[프로그래머스] LEVEL3 단어변환 JAVA

단어 변환

문제링크

풀이

dfs
1. dfs를 활용하여 1자리만 달라서 변경이 가능하면 계속 변경해 나간다.
2. 변경한후 변경한 단어가 target단어라면 끝낸다.
3. target단어 바뀌는 과정들 중 변경 회수가 제일 작은 경우를 찾아 리턴한다.

코드

import java.util.*;

class Solution {
    String[] words;
    String target;
    int N, min;
    boolean[] isSelected;
    public int solution(String begin, String target, String[] words) {
        this.words = words;
        this.target = target;
        N = words.length;
        min = Integer.MAX_VALUE;
        isSelected = new boolean[N];
        
        for (int i = 0; i < N; i++) {
            if (!isSelected[i] && canChange(begin, words[i]))
                dfs(i, words[i], 1);
        }
        
        if (min == Integer.MAX_VALUE) {
            min = 0;
        }
        return min;
    }
    
    public void dfs(int num, String cur, int cnt) {
        if (cnt > min)
            return;
        
        if (compare(cur, target) == 0) {
            min = Math.min(cnt, min);
            return;
        }
        isSelected[num] = true;
        
        for (int i = 0; i < N; i++) {
            if (!isSelected[i] && canChange(cur, words[i]))
                dfs(i, words[i], cnt + 1);
        }
    }
    
    public boolean canChange(String str1, String str2) {
        return compare(str1, str2) == 1;
    }
    
    public int compare(String str1, String str2) {
        int cnt = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                cnt++;
            }
        }
        return cnt;
    }
    
    
}
## ```