LeetCode 127 : Word Ladder(단어 사다리/단어 변환)

https://leetcode.com/problems/word-ladder/description/

 

 

 프로그래머스에 있는 '단어 변환' 문제와 똑같은 문제이다. 다만, 프로그래머스에 있는 문제는 단어의 개수가 최대 50개로, 최대 단어 개수가 5000개인 LeetCode와는 차이가 있다.

 

 프로그래머스에서 먼저 풀고, 단어 개수가 큰 LeetCode에서 점점 최적화를 하면서 풀었다.

 

 

 

 

 

문제

---

(한국어 번역)

 단어 사전인 `wordList`를 이용해 `beginWord`에서 `endWord`까지 변환하는 시퀀스는 다음과 같다.

`beginWord -> S1 -> S2 -> ... -> Sk`

 

• 모든 인접하는 단어 쌍은 한 글자만 다르다.
• 모든 단어는 `wordList`에 속한다. `beginWord`는 `wordList`에 속하지 않아도 된다.
• `Sk == endWord`

 두 단어인 `beginWord`와 `endWord`, 단어 사전인 `wordList`가 주어졌을 때, `beginWord` 에서 `endWord` 로 변환하는 가장 짧은 변환 시퀀스의 단어 수를 리턴하라. 시퀀스가 존재하지 않는다면 0을 리턴하라. 

 

 

 

제한사항

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, wordList[i]는 알파벳 소문자로만 이루어져 있다.
• beginWord != endWord
• wordList에 있는 모든 단어는 중복되어 있지 않다.

 

 

 

예시1

입력

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

출력

5

 

예시2

입력

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

출력

0

 

 

 

 

 

풀이

---

 단어 변환 시퀀스의 최소 길이를 찾는 문제이다. 모든 경우의 수를 탐색하여 최소 길이를 찾기 위해 탐색 알고리즘인 BFS와 DFS를 사용해야 한다.

단어 목록의 길이가 `1 ≤ len(wordList) ≤ 5,000` 으로 효율적인 탐색 알고리즘이 필요하다.

 

 

 

BFS 선택 이유

1. DFS와의 비교

• BFS(너비 우선 탐색)은 특정 노드에서 다른 노드까지의 최단 경로를 찾는 데 적합하다. 가능한 모든 경로를 단계별로 동시에 탐색하고, 목표 노드에 도달하는 순간 최단 경로가 된다.
• DFS(깊이 우선 탐색)은 가능한 모든 경로를 끝까지 탐색한 뒤에 최단 경로를 알 수 있다. 깊이가 깊을수록 불필요한 경로 탐색이 많아지게 된다.

 

2. 시간복잡도

(v : 정점 수 = 단어 목록 길이, E : 간선 수 = 변환 가능한 단어 수)

• BFS : O(V + E)
• DFS : O(V + E)
• DFS는 최단 경로를 찾기 위해 모든 경로를 탐색하므로, 깊이가 깊을수록 비효율적이다.

 

 

코드

from collections import deque, defaultdict

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        
        queue = deque([beginWord])
        visited = set([beginWord])
        answer = 1

        while queue:
            size = len(queue)

            for _ in range(size):
                word = queue.popleft()

                if word == endWord:
                    return answer

                for nextWord in wordList:
                    if nextWord not in visited and self.check(word, nextWord):
                        queue.append(nextWord)
                        visited.add(nextWord)
                
            answer += 1

        return 0
    
    def check(self, s1: str, s2: str) -> bool:
        count = 0

        for i in range(len(s1)):
            if s1[i] != s2[i]:
                count += 1

        return count == 1

 

 

 

결과

• 총 `O(N^2∗M)`의 시간 복잡도를 가진 코드
• 8500ms대의 시간이 나온다. 시간 복잡도를 줄일 필요가 있다.

 

 

 

 

 

 

 

 

최적화1 : 패턴 매칭

---

AS-IS : 문자열 비교

def check(self, s1: str, s2: str) -> bool:
        count = 0

        for i in range(len(s1)):
            if s1[i] != s2[i]:
                count += 1

        return count == 1

• 두 단어를 한 글자씩 차례로 비교하여, 다른 글자가 1글자인지 확인
• 시간 복잡도
  • 한 단계에서의 시간 복잡도 : `O(N * L)` (N: 단어 목록 길이, L : 단어 길이)
  • 전체 시간 복잡도 : `O(N^2 * L)` (여러 단계(N)에 대해 변환 가능한지 확인)

 

TO-BE : 패턴 매칭

def build_Pattern_map(self, wordList: list) -> dict:
        pattern_map = defaultdict(list)

        for word in wordList:
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i + 1 :]
                pattern_map[pattern].append(word)

        return pattern_map

• 각 단어에 대해 가능한 패턴을 미리 생성하고, 패턴에서 가능한 단어를 찾음
• 단어에서 한 글자를 *로 치환한 패턴을 Dictionary에 저장
  • key : 패턴
  • value : 패턴에 해당하는 단어
  • ex) *ot:[hot, dot]
• 시간 복잡도
  • 패턴 생성 : `O(N * L)` (N: 단어 목록 길이, L : 단어 길이)
  • 전체 시간 복잡도 : `O(N * L)` (여러 단계(N)에 대해 단어 길이(L)만큼 확인)

 

 

 

코드

from collections import deque, defaultdict

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        pattern_map = defaultdict(list) # 모든 단어의 패턴을 저장할 해시맵 생성
        
        for word in wordList:
            for i in range(len(beginWord)):
                pattern = word[:i] + '*' + word[i+1:]
                pattern_map[pattern].append(word)

        # BFS 탐색
        queue = deque([beginWord])
        visited = set([beginWord])
        answer = 1

        while queue:
            for _ in range(len(queue)):
                curWord = queue.popleft()

                if curWord == endWord:
                    return answer

                for i in range(len(curWord)):
                    pattern = curWord[:i] + '*' + curWord[i+1:]

                    for nextWord in pattern_map[pattern]:
                        if nextWord not in visited:
                            queue.append(nextWord)
                            visited.add(nextWord)
                
            answer += 1

        return 0

 

 

 

결과

• 총 `O(N∗M)`의 시간 복잡도를 가진 코드
• 120ms대의 시간이 나온다. 많이 개선되었다.

 

 

 

 

 

최적화2 : 양방향 BFS

---

• 시작점(beginWord)과 목표 지점(endWord)에서 동시에 탐색을 시작하여, 두 탐색이 만나는 지점을 찾는다.
• 탐색 큐를 두 개 쓰지만, 탐색 범위를 반으로 줄일 수 있다.
• 전체 시간 복잡도 : `O((N * L) / 2`

 

코드

from collections import deque, defaultdict

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        
        pattern_map = defaultdict(list) # 모든 단어의 패턴을 저장할 해시맵 생성
        
        for word in wordList:
            for i in range(len(beginWord)):
                pattern = word[:i] + '*' + word[i+1:]
                pattern_map[pattern].append(word)

        # 양방향 BFS 탐색
        start_queue = deque([beginWord])
        end_queue = deque([endWord])

        start_visited = set([beginWord])
        end_visited = set([endWord])

        answer = 1

        while start_queue and end_queue:
            if len(start_queue) > len(end_queue):
                start_queue, end_queue = end_queue, start_queue
                start_visited, end_visited = end_visited, start_visited

            for _ in range(len(start_queue)):
                curWord = start_queue.popleft()

                for i in range(len(curWord)):
                    pattern = curWord[:i] + '*' + curWord[i+1:]

                    for nextWord in pattern_map[pattern]:
                        if nextWord in end_visited:
                            return answer + 1

                        if nextWord not in start_visited:
                            start_queue.append(nextWord)
                            start_visited.add(nextWord)

            answer += 1

        return 0

 

 

 

결과

• 총 `O(N∗M/2)`의 시간 복잡도를 가진 코드
• 80ms대의 시간이 나온다. 조금 더 개선되었다.

 

 

 

 

 

결론

 

 

패턴 매칭과 양방향 BFS을 사용하면, 빠르게 최소 길이를 찾을 수 있다.