[Java]프로그래머스-단어변환(DFS/BFS) 문제 풀이 정답 답안

class Solution {
    int answer;
    boolean[] chk;
    public int solution(String begin, String target, String[] words) {

        answer = 51;
        chk = new boolean[words.length];
        dfs(begin, target, 0, chk, words);
        return (answer == 51) ? 0: answer;
    }
    
    void dfs(String presentWord, String target, int n, boolean[] chk, String[] words) {
       
        //탐색이 끝났으면
        if(presentWord.equals(target)) {
            //기존에 찾은 변환과정보다 짧은지 확인 후 업데이트
            answer = (n < answer) ? n : answer; 
            return;
        }
        
        for(int i = 0; i < words.length ; i++) {
            if( !chk[i] && canConvert(presentWord, words[i])) {
                chk[i] = true;
                //계속 탐색.
                dfs(words[i], target, n+1, chk, words);
                chk[i] = false;
            }
        }
        
    }
    
    //두 단어가 한 글자만 차이나는 지 리턴
    boolean canConvert(String s1, String s2) {
        
        int count = 0;
        for(int i = 0; i < s1.length() ; i++) {
            if( s1.charAt(i) != s2.charAt(i) ) {
                count++;
                if(count > 1) {
                    return false;
                }
            }
        }
        return true;
    }
    
}