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

문제

두 개의 단어 begin, target과 단어의 집합 words가 있을 때

begin = "hit"
target = "cog"
words = ["hot","dot","dog","lot","log","cog"]

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

이처럼 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 할 때 최소의 단계를 찾는 문제다.
(단, 모든 단어의 길이는 같으며 변환 방법이 없으면 0을 반환한다.)

접근

보자마자 DFS로 풀 생각부터 했다. 어차피 전부 뒤져야 하기 때문에 전처리는 따로 하지 않았다.

코드

class Solution {
    String target;
    String[] words; 
    boolean[] visited; // 단어 방문 여부
    int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        this.words = words;
        this.target = target;
        visited = new boolean[words.length];
        
        dfs(begin, 0);
        return answer;
    }
    
    public void dfs(String str, int cnt) {
        if (str.equals(target) && (answer == 0 || answer > cnt)) {
            answer = cnt;
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                
                String word = words[i];
                int diff = 0; // 글자 차이
            
                for (int j = 0; j < word.length(); j++) {
                    if (str.charAt(j) != word.charAt(j)) {
                        diff++;
                    
                        if (diff >= 2) {
                            break;
                        }
                    }
                
                    if (j == word.length() - 1 && diff == 1) {
                        dfs(word, cnt + 1);
                    }
                }
                
                visited[i] = false;
            }
        }
    }
}

깜빡하지 않도록 하기 위한 추가적인 메모

• DFS 문제를 풀 때 방문한 정점을 재방문하면 무한루프가 돌게 된다.
  반드시 특정 정점을 방문했는지 체크하는 과정을 잊지 말자.
• 현재 정점과 인접한 지점을 모두 탐색했으면 본인 정점에 대한 방문 여부를 다시 미방문으로 풀어줘야 한다.
  (본인 정점이 나중에 다른 정점으로부터 인접한 정점일 가능성이 있기 때문이다.)