[프로그래머스][단어 변환]-Lv.3

문제링크

문제

접근 방법

DFS 방식으로 접근했다.
checked boolean 변수를 통해서 해당 문자로 바뀌었으면 true 바꿔주고 dfs가 끝나서 돌아오면 false로 바꿔 주었다
-> 현재 문자에서 바꿀 수 있는 문자일 수도 있지만 다른 문자에서도 바꿀 수 있는 문자일 수도 있기 때문이다.

코드

class Solution {
    static int answer = Integer.MAX_VALUE;
    static boolean[] checked;
    public int solution(String begin, String target, String[] words) {
        checked = new boolean[words.length];
        dfs(begin, target,0,words);
        if(answer == Integer.MAX_VALUE){
            answer = 0;
        }
        return answer;
    }
    static void dfs(String change, String target, int count, String[] words){
        if(change.equals(target)){
            answer = Math.min(answer, count);
            return;
        }else{
            for(int i=0; i<words.length; i++){
                if(!checked[i]){     
                    if(check(change, words[i])){
                        checked[i] = true;
                        dfs(words[i], target, count+1, words);
                        checked[i] = false;
                    }
                }
            }
        }
    }
    // 한개를 바꾸면 같은지 확인하는 함수
    static boolean check(String a, String b){
        int cnt = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i)!=b.charAt(i)){
                cnt++;
            }
            if(cnt>1){
                return false;
            }
        }
        return true;
    }
}