알고리즘84 :: 프로그래머스_단어변환

class Solution {
    static int[] visit; 
    static int ans = Integer.MAX_VALUE;
    static void DFS(String[] words, String begin, String target, int cnt) {
        if(begin.equals(target)){
           
            ans = Math.min(ans, cnt);
        }else {
            for(int i=0; i<words.length; i++) {
                int c = 0;
                if(visit[i] == 1) continue;
                for(int j=0; j<begin.length(); j++) {
                    if( begin.charAt(j)!=words[i].charAt(j)) c+=1;
                }
                if(c==1 && visit[i] == 0) {
                    visit[i] = 1;
                    String temp = begin;
                    begin = words[i];
                   
                    DFS(words, begin, target, cnt+1);
                   
                    begin = temp;
                    visit[i] = 0;
                }
            }
        }
    }
    public int solution(String begin, String target, String[] words) {
       
        visit = new int[words.length];
        for(int i=0; i<words.length; i++) {
            int c = 0;
            for(int j=0; j<begin.length(); j++) {
                if(begin.charAt(j)!=words[i].charAt(j)) c+=1;
            }
            if(c==1 && visit[i] == 0) {
                visit[i] = 1;
                
                String temp = begin;
                begin = words[i];
                
                DFS(words, begin, target, 1);
                
                begin = temp;
                visit[i] = 0;
            }
        }
        if(ans == Integer.MAX_VALUE)
            ans = 0;
        return ans;
    }
}

적당히 잘 백트래킹 쓰면 됐다.