프로그래머스 - 단어 변환(Java)

dfs 문제입니다.

 

begin 단어를 words 내부에 있는 단어만을 이용해 target으로 바꾸는 문제입니다.

begin 단어를 words 내부의 단어로 바꿀 때 최대 한 개의 자리수만 바꿀 수 있습니다.

즉, begin과 words를 비교하여 단어 자리가 하나만 차이나는 경우를 탐색하면 됩니다.

단, 이미 탐색했던 곳은 다시 탐색하지 않게 해야 합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static Set<String> wordSet;
    private static boolean[] visited;
    private static int min = Integer.MAX_VALUE;

    public static int solution(String begin, String target, String[] words) {
        int answer = 0;

        wordSet = new HashSet<>();
        for (String word : words) wordSet.add(word);

        // words에 target이 없으면 아예 변환할 수 없음
        if(!wordSet.contains(target)) return 0;

        visited = new boolean[words.length];
        dfs(begin, target, words,0);

        answer = (answer == Integer.MAX_VALUE) ? 0 : min;

        return answer;
    }

    private static void dfs(String begin, String target, String[] words, int depth) {
        if(target.equals(begin)){
            min = Math.min(min, depth);
            return;
        }

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if(!visited[i] && compareString(begin, word)){
                visited[i] = true;
                dfs(word, target, words, depth+1);
                visited[i] = false;
            }

        }
    }

    private static boolean compareString(String str1, String str2){
        int cnt = 0;
        for(int i=0; i<str1.length(); i++){
            char chr1 = str1.charAt(i);
            char chr2 = str2.charAt(i);

            if(chr1 != chr2) cnt++;

            if(cnt > 1) return false;
        }

        return true;
    }
}