단어 변환 [자바]

 

🧫 문제 분석

✔️ 출처

단어 변환 level 3

📖 문제

 

begin 알파벳 중 하나를 words 단어중 하나의 알파벳으로 바꿀 수 있다.

순서는 상관없고, 변경을 최소한으로 해서 target을 만들면 된다. 

 

 

백트래킹하면서 words를 탐색한다. 

 

words 각 단어의 알파벳을 begin의 각 알파벳과 비교해서 

2개이상 다르면 바꾸지 않고 넘어가도록 한다. 

 

만약 알파벳이 1개만 다르다면 그 단어를 begin으로 하고

백트래킹 탐색을 한다. 

---

🔅 문제 풀이

class Solution {
    // 완전탐색
    // 백트래킹
    
    boolean[] visited; 
    int min = Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        char[] word = begin.toCharArray();
        dfs(word, words, target, 0);
        
        return min == Integer.MAX_VALUE ? 0 : min;
    }
    
    private void dfs(char[] start, String[] words, String target, int cnt) {

        // target이면 최솟값 갱신
        if (String.valueOf(start).equals(target)) {
            min = Math.min(min, cnt);
            return;
        }
        
        
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;
            int alphaCnt = 0;
            
            // 한 번에 한개의 알파벳만 변경 가능
            for (int j = 0; j < words[i].length(); j++) {
                if (start[j] != words[i].charAt(j)) {
                    alphaCnt++;
                }
            }
            
            // 다음 단어 알파벳이 2개이상 또는 완전히 같은 경우 바꾸지 않음
            if (alphaCnt > 1 || alphaCnt == 0) continue;
            
            visited[i] = true;
            // 1개만 다른경우 변경
            dfs(words[i].toCharArray(), words, target, cnt + 1);
            visited[i] = false;
        }
        
    }
}

 

❗ 오답노트 / 필요한 지식

1. BFS로도 가능하다.