Graphs: 127. Word Ladder ★★★★★

127. Word Ladder

 

이 문제는 "단어 변환"과 관련된 그래프 탐색 문제입니다. 주어진 시작 단어(beginWord)에서 끝 단어(endWord)까지 최소 몇 번의 단어 변환으로 도달할 수 있는지를 찾는 것입니다. 단, 변환 규칙은 다음과 같습니다:

---

문제 규칙

1. 단어 변환 조건:
   • 변환 시 한 번에 한 글자만 변경할 수 있습니다.
   • 예를 들어, hit에서 hot으로는 변환 가능하지만, hit에서 dot으로는 한 번에 변환할 수 없습니다.
2. 변환 과정 제약:
   • 변환된 중간 단어는 반드시 wordList에 포함되어야 합니다.
   • beginWord는 wordList에 없어도 변환 가능합니다.
3. 목표:
   • beginWord에서 시작하여 endWord로 변환하는 가장 짧은 경로의 길이를 반환합니다.
   • 변환이 불가능한 경우 0을 반환합니다.

---

입력 설명

• beginWord: 시작 단어.
• endWord: 목표 단어.
• wordList: 중간에 사용할 수 있는 단어들의 리스트.

---

출력 설명

• beginWord에서 endWord까지 최소 변환 횟수(단어 개수)를 반환.
• endWord로 도달할 수 없는 경우 0 반환.

 

문제 풀이 방법 (BFS)

이 문제는 그래프 탐색 문제로, BFS를 사용하여 해결합니다:

1. 그래프 생성:
   • 각 단어를 노드로 보고, 한 글자만 다른 단어를 간선으로 연결된 노드로 간주합니다.
2. BFS 탐색:
   • beginWord에서 시작하여 endWord에 도달할 때까지 BFS 탐색을 수행.
   • BFS는 최단 경로 탐색에 적합하므로, 첫 번째로 endWord에 도달하면 그 길이가 최소 경로입니다.
3. 중단 조건:
   • endWord에 도달하면 BFS를 중단하고 현재 경로 길이를 반환.
   • 모든 경로를 탐색했는데 endWord에 도달하지 못하면 0 반환.

1. 풀이 아이디어

• 각 단어를 그래프의 노드로 생각.
• 두 단어가 한 글자만 다르면, 두 노드 사이에 간선이 존재한다고 간주.
• BFS를 사용하여 beginWord에서 시작하여 endWord까지의 최단 경로를 탐색.

---

2. 구체적인 풀이 절차

(1) 기본 조건 확인

• endWord가 wordList에 없으면 변환이 불가능하므로 바로 0을 반환.

(2) 그래프 탐색 준비

• beginWord와 wordList의 단어들을 연결하기 위해 그래프를 구성.
• 단어를 탐색하면서 한 글자만 바꿔가며 변환 가능성을 탐색.

(3) BFS 탐색

• deque를 사용하여 BFS를 수행.
• 각 단어와 변환 횟수를 큐에 저장하며 탐색.
• 처음으로 endWord에 도달하면 현재까지의 변환 횟수를 반환.

(4) 변환 불가능한 경우

• BFS가 끝날 때까지 endWord에 도달하지 못하면 0 반환.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # 기본 조건: endWord가 wordList에 없으면 변환 불가
        if endWord not in wordList:
            return 0

        # 모든 단어를 집합으로 저장 (빠른 검색을 위해)
        wordSet = set(wordList)

        # BFS를 위한 큐 초기화
        q = deque()
        q.append((beginWord, 1))  # (word 현재 단어, steps 현재까지의 변환 횟수)

        while q:
            word, steps = q.popleft()

            # 현재 단어의 각 글자를 하나씩 바꿔가며 탐색
            for i in range(len(word)):
                # 단어의 각 글자를 a부터 z로 변경하여 변환 가능성을 확인.
                for c in 'abcdefghijklmnopqrstuvwxyz':  # 알파벳 a~z로 교체
                    nextWord = word[:i] + c + word[i+1:]  # i번째 글자 변경

                    # endWord에 도달하면 현재 단계의 변환 횟수를 반환
                    # .. nextWord가 endWord라면 변환이 완료된 것이므로 
                    # .. 현재까지의 변환 횟수를 반환.
                    if nextWord == endWord:
                        return steps + 1

                    # 다음 단어가 wordSet에 있고 방문하지 않았으면 탐색
                    if nextWord in wordSet:
                        wordSet.remove(nextWord)  # 방문한 단어는 제거
                        q.append((nextWord, steps + 1))  # 큐에 추가
        
        # BFS 종료 후에도 endWord에 도달하지 못하면 0 반환
        return 0

 

https://youtu.be/h9iTnkgv05E?si=_4E7F1wWzSyFd5k-

 

BFS 사용

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # endWord가 wordList에 없으면 변환이 불가능 (If endWord is not in wordList, transformation is not possible)
        if endWord not in wordList:
            return 0

        # 패턴별로 단어들을 저장하기 위한 딕셔너리 (Dictionary to store words by patterns)
        nei = collections.defaultdict(list)
        
        # beginWord를 wordList에 추가 (Append beginWord to wordList)
        wordList.append(beginWord)

        # 모든 단어에 대해 패턴을 생성하고 패턴에 해당하는 단어를 딕셔너리에 추가
        # (Generate patterns for each word and add words to the corresponding pattern in the dictionary)
        for word in wordList:
            for j in range(len(word)):
                # j번째 문자를 *로 대체하여 패턴 생성 (Create a pattern by replacing the j-th character with '*')
                patten = word[:j] + "*" + word[j+1:]
                nei[patten].append(word)

        # 방문한 단어를 추적하기 위한 집합 (Set to track visited words)
        visit = set([beginWord])
        
        # BFS를 위한 큐 초기화 (Initialize queue for BFS)
        q = deque([beginWord])
        
        # 변환 단계를 추적하는 변수 (Variable to track transformation steps)
        res = 1

        # BFS를 통해 단어 변환 탐색 (Perform BFS to find the shortest transformation)
        while q:
            for i in range(len(q)):  # 현재 레벨의 단어들을 모두 처리 (Process all words at the current level)
                word = q.popleft()
                
                # endWord에 도달하면 현재 변환 단계 반환 (Return the current transformation step if endWord is reached)
                if word == endWord:
                    return res
                
                # 현재 단어에 대해 모든 패턴을 확인 (Check all patterns for the current word)
                for j in range(len(word)):
                    patten = word[:j] + "*" + word[j+1:]
                    
                    # 패턴에 연결된 단어들 중 방문하지 않은 단어를 큐에 추가 (Add unvisited words connected to the pattern to the queue)
                    for neiWord in nei[patten]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            
            # 현재 단계에서 다음 단계로 이동 (Move to the next transformation step)
            res += 1
        
        # endWord를 찾지 못하면 변환이 불가능 (If endWord is not found, return 0)
        return 0

 

DFS

 

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # endWord가 wordList에 없으면 변환이 불가능 (If endWord is not in wordList, transformation is not possible)
        if endWord not in wordList:
            return 0

        # 패턴별로 단어들을 저장하기 위한 딕셔너리 (Dictionary to store words by patterns)
        nei = collections.defaultdict(list)
        
        # beginWord를 wordList에 추가 (Append beginWord to wordList)
        wordList.append(beginWord)

        # 모든 단어에 대해 패턴을 생성하고 패턴에 해당하는 단어를 딕셔너리에 추가
        # (Generate patterns for each word and add words to the corresponding pattern in the dictionary)
        for word in wordList:
            for j in range(len(word)):
                # j번째 문자를 *로 대체하여 패턴 생성 (Create a pattern by replacing the j-th character with '*')
                patten = word[:j] + "*" + word[j+1:]
                nei[patten].append(word)

        # 방문한 단어를 추적하기 위한 집합 (Set to track visited words)
        visit = set()

        # DFS 함수 정의 (Define DFS function)
        def dfs(word, steps):
            # 현재 단어가 endWord라면 변환 단계를 반환 (If the current word is endWord, return steps)
            if word == endWord:
                return steps

            # 현재 단어를 방문으로 표시 (Mark the current word as visited)
            visit.add(word)

            # 현재 단어에 대해 가능한 모든 패턴 탐색 (Explore all patterns for the current word)
            for j in range(len(word)):
                patten = word[:j] + "*" + word[j+1:]
                for neiWord in nei[patten]:
                    if neiWord not in visit:
                        # 재귀적으로 탐색 (Recursively call DFS)
                        res = dfs(neiWord, steps + 1)
                        if res:  # 유효한 경로가 발견되면 반환 (If a valid path is found, return it)
                            return res

            return 0  # 변환 경로가 없으면 0 반환 (Return 0 if no path is found)

        # DFS 시작 (Start DFS)
        return dfs(beginWord, 1)