[LeetCode 풀이/python] 127. Word Ladder (hard)

문제 설명: 사전 wordList 를 이용하여 단어 beginWord 를 endWord 로 변환하는 시퀀스는 다음과 같은 일련의 단어(단어 시퀀스) 를 가리킨다:

• 시퀀스의 첫번째 단어는 beginWord 이다
• 시퀀스의 마지막 단어는 endWord 이다
• 시퀀스에서 인접한 각 단어 쌍은 서로 오직 한 글자씩만 다르다
• 시퀀스의 모든 단어는 wordList 에 존재한다

두 단어 beginWord 와 endWord, 그리고 사전 wordList 가 주어졌을 때, beginWord 에서 endWord 로의 가장 짧은 변환 시퀀스의 길이 (단어의 개수) 를 리턴하고, 만약 그러한 시퀀스가 존재하지 않는 경우 0 을 리턴하시오.

 

(A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

• The first word in the sequence is beginWord.
• The last word in the sequence is endWord.
• Only one letter is different between each adjacent pair of words in the sequence.
• Every word in the sequence is in wordList.

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.)

 

 

예시 1)

입력: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]  -->  출력: 5

설명: One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog" with 5 words.

 

예시 2)

입력: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]  -->  출력: 0

설명: The endWord "cog" is not in wordList, therefore there is no possible transformation.

 

제한 조건:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, wordList[i] 는 영문 소문자로만 구성되어 있음 
• beginWord != endWord
• wordList 의 모든 문자열은 중복되지 않음(unique)

 

------ * ------ * ------ * ------

 

[풀이 1안] -- not a solution!

• 접근법
  • 깊이 우선 탐색(BFS) 을 이용하는 대표적인 문제로서 이전에도 Codility 에서 풀어본 기억이 있으나... 왜 다시 풀려니까 안풀리는 것인가 @_@
  • 왜 BFS 를 이용해서 푸는 것인지 처음엔 이해가 안되었는데, 가장 짧은 경로로 endWord 에 도달하기 위해서임을 깨달음!
    • 더 긴 변환 시퀀스를 통해 endWord 에 도달하는 경로도 존재할 수 있으나, BFS 를 이용하면 각 level (step) 에 대해 전부 탐색한 뒤 다음 level 로 넘어가니까 최단 step 에서 endWord 도달 시 다음 level 로 넘어가지 않고 탐색 종료하게 됨!
  • cur_word 의 변환 결과로 올 수 있는 인접 단어가 될 수 있을지, 사전의 각 단어에 대해 별도 함수 is_adjacent 를 통해 체크하고, 해당 단어를 이전에 방문하지 않았다면 queue 에 삽입하고 탐색 진행!

 

• 코드 구현

from collections import deque
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    wordList = set(wordList)
    queue = deque([[beginWord, 1]])
    visited = set()
        
    while queue:
        cur_word, step = queue.popleft()
        visited.add(cur_word)
            
        if cur_word == endWord:
            return step
            
        for next_word in wordList:
            if (self.is_adjacent(cur_word, next_word)) and (next_word not in visited):
                queue.append([next_word, step+1])
    return 0
        
def is_adjacent(word1, word2):
    cnt = 0 
    for w1, w2 in zip(word1, word2):
        if w1 != w2: cnt +=1
              
    if cnt == 1: return True
    else: return False

 

• 결과
  • 사전 wordList 의 크기가 아주아주 큰 경우에 탐색에 시간이 오래 걸려서 Time Limit Exceed Error 로 통과하지 못함 ㅠ-ㅠ

 

 

[풀이 2안]

• 접근법
  • 특정 단어와 한 문자만 차이나는 인접 단어의 후보를 만드는 과정이 특히 인상 깊어서 기록 겸 풀이 리뷰!
  • 시퀀스의 출발점이 되는 beginWord 와 변환 단계를 나타내는 step 1 를 queue 의 첫 원소로 넣고 탐색을 시작
  • cur_word 가 endWord 와 같아지면 탐색을 종료하고 step 을 결과로 리턴 (종료 조건)
  • 그렇지 않은 경우, cur_word 의 각 문자를 다른 알파벳(a-z) 으로 바꾼 단어, 곧 cur_word 의 인접 단어가 될 수 있는 후보 next_word 각각에 대해 해당 단어가 사전 wordList 에 존재하는 경우 해당 단어를 queue 에 넣고 탐색을 진행

 

• 코드 구현

from collections import deque
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    wordList = set(wordList)
    queue = deque([[beginWord, 1]])
        
    while queue:
        cur_word, step = queue.popleft()
            
        if cur_word == endWord:
            return step
            
        for i in range(len(cur_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = cur_word[:i] + c + cur_word[i+1:]
                    
                if next_word in wordList:
                    wordList.remove(next_word)
                    queue.append([next_word, step+1])
    return 0

 

• 결과
  • next_word 를 고려하는 방식이 신박...!
  • 사전 wordList 의 단어가 많지 않을 경우에 사전에 없는 수많은 단어들까지 불필요하게 고려하게 되는 듯 했으나, 반대로 wordList 의 단어가 아주 많은 경우 해당 배열을 모두 탐색하지 않고 알파벳 문자 수(26) * 현재 단어의 문자 수(<=10) 개의 경우의 수만 고려하면 되므로 계산량 면에서 훨씬 이득이었음...!!

•