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

📝 문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 주어질 때, begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾는 문제입니다. 한 번에 한 개의 알파벳만 바꿀 수 있으며, words에 있는 단어로만 변환할 수 있습니다.

---

💡 접근 방식

1. 탐색 전략: DFS와 백트래킹

한 단어에서 다음 단어로 넘어가는 모든 경우의 수를 고려해야 하므로 DFS를 선택했습니다. 특히, 다른 경로에서도 해당 단어를 다시 사용할 수 있도록 백트래킹(visit[i] = false)을 적용하여 모든 가능성을 탐색했습니다.

2. 변환 가능 조건 판단

현재 단어와 다음 단어를 비교하여 딱 한 글자만 다른 경우에만 변환이 가능합니다. 이를 위해 이중 for문을 사용하여 자릿수별로 비교하고 차이가 1인 경우만 재귀 호출을 진행했습니다.

3. 최소 단계 업데이트

목표 단어(target)에 도달했을 때, 현재까지의 깊이(now)와 기존의 answer를 비교하여 더 작은 값으로 갱신했습니다.

---

💻 구현 코드

import java.util.*;

class Solution {
    static int answer;
    
    public int solution(String begin, String target, String[] words) {
        answer = Integer.MAX_VALUE;
        
        boolean[] visit = new boolean[words.length];
        dfs(0, words.length, begin, target, visit, words);
        if(answer == Integer.MAX_VALUE) return 0;
        
        return answer;
    }
    
    public void dfs(int now, int n, String begin, String target, boolean[] visit, String[] words) {
        
        if(begin.equals(target)) {
            answer = Math.min(answer, now);
            return;
        }
        else {
            for(int i=0; i<n; i++) {
                if(visit[i]) continue;
                
                String word = words[i];
                int cnt = 0;
                
                for(int j=0; j<begin.length(); j++) {
                    if(begin.charAt(j) != word.charAt(j)) {
                        cnt++;
                    }
                }
                
                if(cnt != 1) continue;
                
                visit[i] = true;
                dfs(now+1, n, word, target, visit, words);
                visit[i] = false;
            }
        }
    }
}

---

✨ 느낀 점

• 백트래킹의 이해: 방문 처리를 다시 해제해 주는 과정이 왜 필요한지, 이를 통해 어떻게 모든 경로를 탐색할 수 있는지 깊이 있게 이해할 수 있었습니다.

• 최단 거리 문제의 특성: DFS로 풀었지만, 최단 거리 문제에서는 BFS가 가지는 강점(답을 찾는 즉시 종료 가능)에 대해서도 다시 한번 생각해보게 되었습니다.

• 알고리즘의 확장: 오늘 배운 DFS 기술을 다양한 문제에 응용할 수 있다는 자신감을 얻었습니다.