[JAVA/DFS]단어 변환

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

코딩테스트 연습 - 단어 변환

 

 

 

 

class Solution {
    
    int answer = Integer.MAX_VALUE;
    boolean[] converted;
    
    public int solution(String begin, String target, String[] words) {
        converted = new boolean[words.length];
        
        dfs(begin, target, words, 0);
        
        // answer이 바뀌지 않았다면 return 0
        if(answer == Integer.MAX_VALUE) {
            answer = 0;
        }
        
        return answer;
    }
    
    public void dfs(String word, String target, String[] words, int cnt) {
        if(word.equals(target)) {
            // 최소값일 경우 answer 갱신
            answer = Math.min(cnt, answer);
            return;
        }
        
        for(int i=0; i<words.length; i++) {
            // 겹치는 단어 수
            String w = words[i];
            int notDuplicated = 0;
            
            for(int j=0; j<word.length(); j++) {
                if(word.charAt(j) != w.charAt(j)) {
                    notDuplicated++;
                    if(notDuplicated >= 2) {
                        // 두 글자 이상 겹치면 break
                        break;
                    }
                }
            }
            
            if(notDuplicated == 1 && !converted[i]) {
                converted[i] = true;
                dfs(w, target, words, cnt+1);
                converted[i] = false;
            } 
        }
    }
}