[프로그래머스] 단어 변환 (JAVA)

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 단어 변환

---

[풀이]

1. 원하는 단어와 같아지면 현재까지의 횟수를 answer에 담고 리턴한다.

2. 이미 사용한 단어라면 돌아간다.

3. 단어끼리 비교해서 다른 알파벳이 몇개인지 확인한다.

4. 3. 에서 확인한 다른 단어의 개수가 1개라면 변환 가능한 단어이므로 해당 단어를 탐색한 것으로 표시하고  dfs 탐색을 한다.

5. 1. ~ 4. 를 포함한 dfs 함수를 만들어준다.

6. dfs를 탐색해서 해당 결과를 리턴해준다.

[접근]

1. DFS로 문제를 풀면 되겠다고 생각하였다.

[코드]

class Solution {
    static boolean[] visit;
    static int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        visit = new boolean[words.length];

        dfs(begin, target, words, 0);
        
        return answer;
    }
    
    public static void dfs(String now, String target, String[] words, int cnt) {
        // 원하는 단어와 같아지면
        if (now.equals(target)) {
            answer = cnt;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            // 이미 쓴 단어면 넘어가기
            if (visit[i]) {
                continue;
            }

            // 단어끼리 다른 개수 찾기
            int k = 0;
            for (int j = 0; j < now.length(); j++) {
                if (now.charAt(j) != words[i].charAt(j)) {
                    k++;
                }
            }

            // 다른게 1개라면 탐색
            if (k == 1) {
                visit[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visit[i] = false;
            }
        }
    }
}