깊이/너비 우선 탐색(DFS/BFS) - 단어 변환

이 문제는 BFS(너비 우선 탐색)를 이용하여 단어 변환를 풀어야한다. BFS는 Queue 방식으로 최단 경로를 찾는데 적합한 알고리즘이다. 이 문제는 '가장 짧은 변환 과정'을 찾는 데 좋기 때문이다. 주어진 단어들을 그래프의 노드로 생각하고, 한 번에 한 개의 알파벳만 바꿀 수 있는 변환이 필요하다.

 

mport java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        // 변환 가능한 단어를 저장할 리스트
        List<String> wordList = Arrays.asList(words);
        
        // BFS 탐색을 위한 큐와 방문 배열
        Queue<String> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        
        // 큐에 시작 단어와 단계 1을 추가
        queue.offer(begin);
        int level = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                
                // 현재 단어와 변환 가능한 모든 단어를 확인
                for (int j = 0; j < words.length; j++) {
                    if (!visited[j] && canTransform(current, words[j])) {
                        // 변환 가능한 단어를 큐에 추가
                        if (words[j].equals(target)) {
                            return level;
                        }
                        queue.offer(words[j]);
                        visited[j] = true;
                    }
                }
            }
        }
        
        // 변환할 수 없는 경우 0 반환
        return 0;
    }
    
    // 두 단어가 한 자리만 다른지 확인하는 함수
    private boolean canTransform(String from, String to) {
        int diffCount = 0;
        for (int i = 0; i < from.length(); i++) {
            if (from.charAt(i) != to.charAt(i)) {
                diffCount++;
                if (diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }
}

문제 풀이

1, canTransForm() 함수에 두 단어의 각 문제 위치를 비교하여 차이가 한 자리만 있는지 확인한다.

2. solution() 함수에 BFS 탐색을 시작하며, 큐에는 현재 변환 가능한 단어를 저장하고, 'visted' 배열을 통해 방문 여부를 관리한다.

3. 큐에서 단어를 꺼내고, 그 단어와 변환 가능한 모든 단어를 확인하여 투표 단어가 발견되면 현재 단게( Level )를 반환한다.

4. 큐가 비어도 목표 단어를 찾지 못하면 변환이 불가능하므로 0을 반환한다.

 

 

 

Script

이 문제를 풀때 DFS 와 BFS 어떤 것을 사용해야할지 생각을 해보았다. 최단 거리로 문제를 풀어야 하기 때문에 Queue로 문제를 풀면 좋겠다고 생각을 하였다. 막상 문제를 풀려고 하니 제대로 안되다 보니 그림을 그려서 문제를 풀어보는것도 좋은 방법인거 같다.