[프로그래머스] 43163. 단어 변환

문제 링크

[프로그래머스] 43163. 단어 변환

풀이 과정

주어진 words 배열 안에서 단어 변환이 가능한 모든 경우를 dfs 를 통해 확인합니다. 변환하려는 단어가 target 인 경우, 변환 횟수를 answer 에 담아 저장해 둡니다.

코드

public class Main {
    static int answer = Integer.MAX_VALUE;

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

        for (int i = 0; i < words.length; i++) {
            dfs(begin, target, i, words, visit, 0);
        }

        answer = answer == Integer.MAX_VALUE ? 0 : answer;

        return answer;
    }

    public static void dfs(String now, String target, int idx, String[] words, boolean[] visit, int depth) {
        visit[idx] = true;

        int cnt = 0;
        for (int i = 0; i < words[idx].length(); i++) {
            if (cnt >= 2) break;

            if (now.charAt(i) != words[idx].charAt(i)) {
                cnt++;
            }
        }

        if (cnt == 1) {
            if (words[idx].equals(target)) {
                visit[idx] = false;

                answer = Math.min(answer, depth + 1);

                return;
            }

            for (int i = 0; i < words.length; i++) {
                if (!visit[i]) {
                    dfs(words[idx], target, i, words, visit, depth + 1);
                }
            }
        }

        visit[idx] = false;
    }

    public static void main(String[] args) {
        String begin = "hit";
        String target = "cog";

        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
//        String[] words = {"hot", "dot", "dog", "lot", "log"};

        solution(begin, target, words);
    }
}