Lv.3 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

class Solution {
    public int solution(String begin, String target, String[] words) {
        boolean[] visits = new boolean[words.length]; // 방문 처리 배열
        int result = dfs(words, visits, begin, target, 0); // 결과 값
        
        if (result != 51) {
            return result;
        }
        return 0; // result가 51인 경우는 target으로 변환 못한 경우
    }
    
    static int dfs(String[] words, boolean[] visits, String begin, String target, int cnt) {
        if (begin.equals(target)) { // target으로 변환 가능하면 변환 횟수 리턴
            return cnt;
        }
        int result = 51; // 변환할 수 있는 최대 횟수: 50번
        
        for (int i = 0; i < words.length; i++) {
            if (visits[i] || !canConvert(begin, words[i])) { // 방문 했는지 || 변환 가능한지
                continue;
            }
            visits[i] = true; // 한번 변환 했던 것은 방문처리
            int tmp = dfs(words, visits, words[i], target, cnt + 1);
            visits[i] = false;
            if (result > tmp) { // result와 변환 횟수 비교 후 더 작은 값 저장
                result = tmp;
            }
        }
        
        return result; // target까지 변환 못한 경우는 51, 변환한 경우는 변환 횟수 중 최솟값 리턴
    }
    
    // 한개의 문자만 달라야 변환 가능
    // (같은 문자끼리 비교하는 경우는 없음)
    static boolean canConvert(String str1, String str2) {
        boolean run = false; // 다른 문자를 찾으면 run = true;
        
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) == str2.charAt(i)) { // 문자가 같을 땐 넘어가기
                continue;
            }
            if (run) { // run이 true일 때 = 이미 다른 문자를 찾은 경우
                return false; // 다른 문자가 2개 이상이므로 변환 불가능
            }
            run = true;
        }
        
        return true;
    }
}