[프로그래머스] (깊이/너비 우선 탐색) 단어 변환

단어집합을 탐색해 나가면서 한 글자만 다른 단어를 찾아낸 후, 그 단어로 다시 탐색을 시작하여

최종 타겟단어와 일치할 때까지의 탐색 깊이를 측정한다.

 

단, 최종 타겟 단어에 이르기 까지 여러가지 경로가 있을 수 있는데, 이 중 가장 짧은 길이를 반환하면 된다.

 

 

타겟 단어와 1개의 알파벳만 다른지 판별하는 함수는 별도로 작성했다.

class Solution {
    int answer = Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {
        boolean[] isChecked = new boolean[words.length];
        dfs(begin, target, words, isChecked, 0);
        if (answer == Integer.MAX_VALUE) {
            return 0;
        }
        return answer;
    }
    
    public void dfs(String begin, String target, String[] words, boolean[] isChecked, int cnt) {
        if(begin.equals(target) ) {
            answer = Math.min(answer, cnt);
            return;
        }

        for (int i = 0; i < words.length; i++) {
            String w = words[i];

            if(isChecked[i] == false && findWord(w, begin)) {
                isChecked[i] = true;
                dfs(w, target, words, isChecked, cnt+1);
                isChecked[i] = false;
            }
        }
        return;
    }

    public boolean findWord(String s1, String s2) {
        int diffCnt = 0;
        for (int i = 0; i < s1.length(); i++) {
             if(s1.charAt(i) != s2.charAt(i)) {
                 diffCnt++;
             }
        }
        if(diffCnt == 1) {
            return true;
        } else {
            return false;
        }
    }
}

 

출처: 프로그래머스 코딩 테스트 연습, 
https://programmers.co.kr/learn/challenges