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

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

프로그래머스

풀이:

class Solution {
    int answer = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        dfs(begin, target, words, visited, 0);
        if(answer == Integer.MAX_VALUE) answer = 0; // 변환할 수 없는 경우
        return answer;
    }

    public void dfs(String now, String target, String[] words, boolean[] visited, int time){
        if(now.equals(target)){
            answer = Math.min(answer, time);
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if(visited[i]) continue;
            String word = words[i];
            int cnt = 0;
            for (int j = 0; j < word.length(); j++) {
                if(now.charAt(j) == word.charAt(j)) cnt++;
            }
            if(cnt == word.length() - 1){ // 1개 알파벳만 다른 경우
                visited[i] = true;
                dfs(word, target, words, visited, time+1);
                visited[i] = false;
            }
        }
    }
}

public class Main {

    public static void main(String[] args){
        Solution solution = new Solution();
        int answer = solution.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"});
        System.out.println("answer = " + answer);
    }

}