프로그래머스 - DFS - 단어 변환

programmers.co.kr/learn/courses/30/lessons/43163

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

public class 단어_변환 {
    public static void main(String[] args) {
        단어_변환 o = new 단어_변환();
        System.out.println(o.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}));
        //System.out.println(o.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}));
    }

    private boolean[] isVisit;
    private String[] words;
    private String target;
    private String begin;
    private int min = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        this.begin = begin;
        this.target = target;
        this.words = words;
        isVisit = new boolean[words.length];

        dfs(begin, 0, 0);
        if(min == Integer.MAX_VALUE) {
            min = 0;
        }

        return min;
    }

    private void dfs(String curWord, int index, int count) {
        if(curWord.equals(target)) {
            if(count < min) {
                min = count;
            }
        }

        for(int i=0; i<words.length; i++) {
            if(!isVisit[i] && isChangeable(curWord, i)) {
                isVisit[i] = true;
                dfs(words[i], i, ++count);
                isVisit[i] = false;
                count--;
            }
        }
    }

    private boolean isChangeable(String curWord, int changeableIndex) {
        String changeableWord = words[changeableIndex];
        int count = 0;

        for(int i=0; i<curWord.length(); i++) {
            if(curWord.charAt(i) != changeableWord.charAt(i)) {
                count++;
            }
        }

        return count == 1;
    }
}

알고리즘

• 완전탐색, DFS
• 단어를 기준으로 순회하여 다음 단어로 갈 수 있는지 확인한다(단어중 문자 하나만 다르면 이동할 수 있다)
• DFS를 하며 백트래킹 됐을때, 변경횟수와 방문상태를 원래상태로 돌려놔야한다.