[LeetCode] 126. Word Ladder II

😎풀이

가장 중요한 순서는 다음과 같다.

1. 한 글자마다 다른 알파벳으로 교체해가며 endWord까지 변경되는 과정 기록
2. 최단 경로를 찾아 반환

function findLadders(beginWord: string, endWord: string, wordList: string[]): string[][] {
    // wordList를 Set으로 변환하여 검색 효율을 높임
    const wordSet = new Set(wordList);
    
    // endWord가 wordList에 없으면 변환 불가능
    if (!wordSet.has(endWord)) {
        return [];
    }
    
    // 결과를 저장할 배열
    const result: string[][] = [];
    
    // 각 단어까지의 최단 거리를 저장하는 Map
    const distance = new Map<string, number>();
    // 각 단어의 이전 단어들을 저장하는 Map
    const parents = new Map<string, Set<string>>();
    
    // BFS를 위한 큐 초기화
    const queue: string[] = [beginWord];
    distance.set(beginWord, 0);
    
    // BFS로 최단 거리 찾기
    while (queue.length > 0) {
        const currentWord = queue.shift()!;
        const currentDistance = distance.get(currentWord)!;
        
        // endWord에 도달했다면 더 이상 탐색할 필요 없음
        if (currentWord === endWord) break;
        
        // 현재 단어에서 한 글자만 다른 모든 가능한 단어 탐색
        for (let i = 0; i < currentWord.length; i++) {
            for (let c = 97; c <= 122; c++) { // 'a'부터 'z'까지
                const newWord = 
                    currentWord.slice(0, i) + 
                    String.fromCharCode(c) + 
                    currentWord.slice(i + 1);
                
                if (!wordSet.has(newWord)) continue;
                
                // 새로운 단어를 처음 발견했을 때
                if (!distance.has(newWord)) {
                    distance.set(newWord, currentDistance + 1);
                    queue.push(newWord);
                    parents.set(newWord, new Set([currentWord]));
                }
                // 같은 거리로 도달할 수 있는 다른 경로를 발견했을 때
                else if (distance.get(newWord) === currentDistance + 1) {
                    parents.get(newWord)!.add(currentWord);
                }
            }
        }
    }
    
    // endWord까지 도달할 수 없는 경우
    if (!distance.has(endWord)) {
        return [];
    }
    
    // DFS로 모든 최단 경로 찾기
    function buildPaths(word: string, path: string[]): void {
        if (word === beginWord) {
            result.push([...path].reverse());
            return;
        }
        
        const parentWords = parents.get(word);
        if (!parentWords) return;
        
        for (const parentWord of parentWords) {
            path.push(parentWord);
            buildPaths(parentWord, path);
            path.pop();
        }
    }
    
    buildPaths(endWord, [endWord]);
    return result;
}