[Programmers] 단어 변환 DFS 풀이 (Java)

단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

DFS 풀이

begin 과 한 글자 차이가 나는 단어를 찾고 그 단어에서 부터 모든 words 와 (역시 한 글자 차이가 나는 ) 비교해 가며 구현한다. 이 때 정답은 가장 적은 변화로 target 을 찾는 경우의 수를 구하는 문제다.

 

우선 처음 for 문으로 모든 words 에 대해 비교한다. 즉 begin -> 1번 단어 -> .... -> 종료 와 begin -> 2번 단어 -> ... -> 종료 와 같이 begin 바로 다음에 비교할 단어를 words 의 모든 단어를 대상으로 하는 것이다.

 

이 구현대로 하면 1 번 단어 -> 2번 단어와 2번 단어 -> 1번 단어와 중복되는 계산이 있을 수도 있다. 그러나 주어진 words 의 길이가 적고 (문제에선 3개 이상 50개 이하의 단어가 있다고 했다.) 이미 1번 단어 -> 2번 단어로 계산하고 있는 재귀에서는 2번 단어 -> 1번 단어와 같은 루프는 돌지 않는다. (visited 배열을 for loop 안에 쓴 것을 보면 된다. 캐시 값을 for loop 에서 초기화 하였다.)

 

그리고 가장 적은 변화가 필요하므로 min 함수로 정답 값을 비교하였다. 정답은 전체 배열 크기를 넘어설 일이 없으므로 초기화를 words.length + 1 만큼 해 주었다. 만약 이 값이 그대로 나온다면 target 을 찾지 못한 것으로 보았다.

class Solution {

    public boolean isDiffOneChar(String str1, String str2) {
        int cnt = 0;
        for (int i = 0; i < str1.length() && cnt < 2; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                cnt++;
            }
        }
        return cnt == 1;
    }

    public int dfs(String begin, String target, int index, String[] words, boolean[] visited, int cnt) {

        if (begin.equals(target)) {
            return cnt;
        }

        if (visited[index]) {
            return cnt;
        }

        visited[index] = true;

        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            if (index != i && isDiffOneChar(begin, words[i]) && !visited[i]) {
                ans = dfs(words[i], target, i, words, visited, cnt + 1);
            }
        }
        return ans;
    }

    public int solution(String begin, String target, String[] words) {
        int answer = words.length + 1;

        for (int i = 0; i < words.length; i++) {
            boolean[] visited = new boolean[words.length];
            if (isDiffOneChar(begin, words[i])) {
                answer = Math.min(answer, dfs(words[i], target, i, words, visited, 1));
            }
        }

        if (answer == words.length + 1) {
            return 0;
        }
        return answer;
    }
}