Word Ladder
beginWord와 endWord라는 두 단어와 단어 목록 wordList가 주어집니다. 사다리는 beginWord로 시작하고 endWord로 끝나며, 각 단어에서 다음 단어로 갈 때 정확히 한 글자만 바뀌는 단어의 연속입니다. beginWord 이후의 모든 단어는 wordList에 포함되어야 합니다.
양쪽 끝 단어를 모두 포함해 가장 짧은 사다리를 이루는 단어의 개수를 반환하고, 사다리가 없으면 0을 반환합니다. 예를 들어, cold, cord, card는 단어 3개로 이루어진 사다리입니다. beginWord는 wordList에 없어도 되지만, endWord는 있어야 합니다.
함수
- beginWordstring
- 사다리의 첫 번째 단어
- endWordstring
- 사다리가 도달해야 하는 단어
- wordListstring-array
- 모든 후속 단계가 가져와야 하는 단어들
- 반환값integer
- 가장 짧은 단어 사다리에 있는 단어의 개수, 없으면 0
제약 조건
1 ≤ beginWord.length ≤ 10endWord와wordList의 모든 단어는beginWord와 길이가 같습니다.1 ≤ wordList.length ≤ 5000- 모든 단어는 소문자 영어 문자만 포함합니다.
beginWord != endWordwordList에 있는 단어들은 모두 서로 다릅니다.beginWord는 그중 하나일 수도 있고 아닐 수도 있습니다.
예제
- 입력
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- 출력
- 4
- 설명
lead와gold는 세 글자가 다르므로, 사다리에는 최소 4개의 단어가 필요하며lead,load,goad,gold는 정확히 4개입니다.lend와lewd도lead와 한 글자만 다르지만, 둘 다 새로운 곳으로 이어지지 않으며bold는gold에서만 도달할 수 있습니다.
- 입력
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- 출력
- 0
- 설명
cat,cot,cog는dog와 한 글자 차이까지 가까워지지만, 목록에dog가 없으므로 그곳에서 끝나는 사다리는 없습니다.
- 입력
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- 출력
- 3
- 설명
ab,ad,cd와ab,cb,cd는 모두 단어 3개를 사용합니다.ab도 목록에 있지만, 어느 쪽이든 시작 단어는 한 번만 셉니다.
제출 시 숨은 테스트 +14개
후속 질문
길이만이 아니라, 최단 단어 사다리 하나를 단어 순서대로 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 단어를 하나의 점으로 나타내고, 정확히 한 글자만 다른 두 단어 사이에 선을 그려 보세요. 이 그림에서 사다리란 무엇이며, 가장 짧은 사다리는 무엇일까요?
가장 짧은 사다리는 선의 수가 가장 적은 경로이며, 모든 선은 동일하게 계산됩니다. 너비 우선 탐색은 두 단계 떨어진 단어에 도달하기 전에 한 단계 떨어진 모든 단어에 도달하므로,
endWord에 처음 도달했을 때 가장 적은 단계를 거친 것입니다. 단어에 처음 도달하는 순간 방문한 것으로 표시하세요.단어를 전체 목록과 하나씩 비교해 이웃을 찾는 것은 느립니다. 대신 한 번에 한 글자씩 숨깁니다.
hot,hat,hit는 모두h*t가 됩니다. 각 단어를 그 단어의 모든 패턴에 해당하는 버킷에 넣습니다. 한 단어의 이웃은 그 단어가 속한 버킷에 있는 다른 단어들입니다.beginWord에서 시작해 레벨별로 탐색하고 레벨 수를 셉니다.
풀이
단어들을 그래프의 노드로 보고, 한 글자만 다른 두 단어 사이에 간선이 있다고 생각하세요. 그러면 사다리는 beginWord에서 endWord까지의 경로이고, 모든 간선의 비용은 같으므로 최단 사다리는 간선 수가 가장 적은 경로입니다. 너비 우선 탐색은 바로 이를 찾습니다. 이 문제를 어렵게 만드는 것은 간선을 빠르게 찾는 것입니다. 단어 5,000개의 모든 쌍을 비교하면 2,500만 번 비교해야 하므로, 가장 좋은 해결 방법은 와일드카드 패턴을 통해 이웃 단어를 찾는 것입니다. 아래에서 n은 단어의 수이고 L은 단어의 길이입니다.
깊이 우선 탐색으로 모든 사다리를 시도하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
beginWord에서 시작합니다. 현재 단어에서 한 글자만 다른 아직 사용하지 않은 단어를 모두 시도하고, 그 단어에서 더 깊이 탐색합니다. endWord에 도달하면 지금까지 찾은 것 중 가장 짧은 사다리라면 그 길이를 기록합니다. 현재 경로의 단어는 사용한 것으로 표시해 사다리가 자기 자신으로 되돌아오지 않게 하고, 해당 단어에서 되돌아 나올 때는 사용 가능하도록 표시를 해제해 다른 사다리에서 쓸 수 있게 합니다. best개의 단어로 이루어진 사다리를 찾으면 이미 best-1개의 단어가 있는 경로는 더 이상 확장하지 않습니다. 더 짧은 사다리로 완성될 수 없기 때문입니다.
이 방법이 올바른 이유는 단어를 반복하지 않는 모든 사다리를 시도하고, 최단 사다리는 단어를 반복하지 않기 때문입니다. 같은 단어가 두 번 나타난다면 두 단어 사이의 부분을 제거해 더 짧은 사다리를 만들 수 있습니다.
사다리의 수가 폭발적으로 늘어나기 때문에 느립니다. 첫 글자만 다른 26개의 단어 aaa, baa부터 zaa까지를 생각해 보세요. 모든 쌍은 한 글자만 다르므로, 탐색은 다음 단계로 넘어가기 전에 이 단어들을 어떤 순서로든 방문할 수 있고, 26개의 단어는 약 4 × 10^26가지 순서로 나열할 수 있습니다. 가지치기는 사다리를 하나 찾은 뒤에야 도움이 됩니다. endWord에 전혀 도달할 수 없는 경우에는 가지치기가 한 번도 이루어지지 않으며, 단어 목록이 34개만 있어도 탐색을 끝내기에는 이미 너무 많습니다. 재귀 깊이도 사다리 길이만큼 깊어지며, 사다리의 단어 수가 수천 개일 수도 있습니다.
알고리즘
beginWord가 목록에 있으면 사용됨으로 표시하고,best를 0으로 설정합니다.search(word, length)를 작성합니다.word가endWord이면length가best보다 작을 때best를length로 설정하고 반환합니다.best가 0이 아니고length + 1 ≥ best이면 반환합니다. 이 경로로는 최솟값을 갱신할 수 없습니다.word에서 한 글자만 다른 사용되지 않은 모든 단어에 대해, 해당 단어를 사용됨으로 표시하고search(next, length + 1)을 호출한 다음 사용되지 않음으로 표시합니다.search(beginWord, 1)을 호출하고best를 반환합니다. 사다리가 없으면best는 0으로 유지됩니다.
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
best = 0 # words in the shortest sequence found so far, 0 while there is none
used = [word == beginWord for word in wordList] # words on the current path
def search(word, length):
nonlocal best
if word == endWord:
if best == 0 or length < best:
best = length
return
if best != 0 and length + 1 >= best:
return # any longer path cannot beat the best one
for i, candidate in enumerate(wordList):
if not used[i] and one_letter_apart(word, candidate):
used[i] = True
search(candidate, length + 1)
used[i] = False # free the word for other paths
search(beginWord, 1)
return best너비 우선 탐색, 모든 쌍 비교
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
너비 우선 탐색은 거리에 따라 단어를 순서대로 탐색합니다. 먼저 beginWord이며, 사다리의 길이는 1단어입니다. 그런 다음 거리가 1글자인 모든 단어를 탐색하며, 사다리의 길이는 2입니다. 이어서 그 단어들에서 거리가 1글자인 새로운 단어를 모두 탐색하며, 사다리의 길이는 3이 되는 식으로 계속됩니다. 큐는 이 순서를 유지합니다. 단어는 큐에 들어간 순서대로 빠져나오므로 거리 d인 모든 단어가 거리 d + 1인 단어보다 먼저 빠져나옵니다.
이 순서 덕분에 BFS가 처음 찾는 사다리가 최단 사다리입니다. 어떤 단어에 거리 d로 처음 도달했을 때는 d보다 가까운 모든 단어를 이미 탐색했으므로, 그 단어로 가는 더 짧은 사다리가 있었다면 탐색 과정에서 그 단어에 더 일찍 도달했을 것입니다. 같은 논리에 따라 단어를 큐에 넣는 순간 방문한 것으로 표시해도 안전합니다. 해당 단어까지의 거리는 확정되며, 나중에 다시 도달하면 거리는 더 길어질 수밖에 없습니다. 따라서 각 단어는 큐에 한 번만 들어가며, endWord가 이웃으로 나타나는 즉시 그 거리가 답이 됩니다.
이 버전은 단어를 큐에서 꺼낼 때마다 목록의 모든 단어와 글자별로 비교하고, 두 번째 차이점이 발견되면 비교를 멈춰 이웃을 찾습니다. 큐에서 빠져나오는 최대 n개의 단어 각각에 대해 최대 L개의 글자를 비교하는 작업을 최대 n번 수행하므로, 전체 시간 복잡도는 O(n² × L)입니다. 단어가 5,000개이고 탐색 과정에서 대부분의 단어를 방문한다면, 단어 비교는 최대 2,500만 번입니다. 컴파일 언어에서는 이 작업을 빠르게 끝낼 수 있지만, Python에서는 가장 큰 테스트에서 몇 초가 걸립니다.
알고리즘
endWord가wordList에 없으면 0을 반환합니다.beginWord를 길이 1과 함께 큐에 넣습니다. 목록에 있으면 방문한 것으로 표시합니다.- 큐에서 다음 단어와 그 길이를 가져옵니다.
- 목록에서 아직 방문하지 않은 모든 단어와 비교합니다. 정확히 한 글자만 다른 단어가
endWord이면 길이 + 1을 반환합니다. 그렇지 않으면 방문한 것으로 표시하고 길이 + 1과 함께 추가합니다. - 큐가 비면
endWord에 도달할 수 없습니다. 0을 반환합니다.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
if endWord not in wordList:
return 0
visited = [word == beginWord for word in wordList]
queue = deque([(beginWord, 1)]) # (word, words in the sequence up to it)
while queue:
word, length = queue.popleft()
# Compare against every word to find the neighbours.
for i, candidate in enumerate(wordList):
if not visited[i] and one_letter_apart(word, candidate):
if candidate == endWord:
return length + 1
visited[i] = True
queue.append((candidate, length + 1))
return 0와일드카드 버킷을 이용한 너비 우선 탐색
핵심 아이디어
너비 우선 탐색은 유지하면서 이웃을 효율적으로 찾으세요. 두 단어에서 같은 위치의 글자를 숨겼을 때 두 단어가 같아지는 경우에만 두 단어는 정확히 한 글자 차이입니다. hot과 hit는 둘 다 h*t가 됩니다. 그러므로 모든 단어에 숨길 위치마다 하나씩 L개의 패턴을 부여하고, 각 패턴의 버킷에 해당 단어를 추가하세요. 단어의 이웃은 해당 단어의 L개 버킷에 있는 다른 단어들이며, 전체 목록을 훑는 대신 L번의 해시 조회로 찾습니다.
첫 번째 예시에서 탐색하는 방법은 다음과 같습니다. lead에는 *ead, l*ad, le*d, lea* 패턴이 있습니다. l*ad 버킷에는 load가 있고 le*d 버킷에는 lend와 lewd가 있으므로, 레벨 2에는 이 세 단어가 있습니다. load에서 *oad 버킷을 통해 레벨 3의 goad를 찾고, goad에서 go*d를 통해 레벨 4의 gold를 찾습니다.
한 가지 더 절약할 수 있습니다. 단어의 버킷을 탐색했다면 그 안의 모든 단어에 이미 도달한 것이므로 버킷을 비우세요. 같은 패턴을 공유하는 나중의 단어들도 어차피 그곳에서 새로운 단어를 찾을 수 없습니다. aaa부터 zaa까지 26개 단어가 *aa를 공유하는 테스트에서는 26개 단어가 든 버킷을 26번이 아니라 한 번만 탐색합니다. 따라서 탐색 중 각 n × L 버킷 항목은 최대 한 번만 읽습니다.
패턴을 만들려면 글자가 L개인 문자열 n × L개가 필요하며, 시간과 공간은 O(n × L²)입니다. 탐색에도 동일한 비용이 듭니다. 큐에서 꺼내는 각 단어마다 L개의 패턴을 다시 만듭니다. 글자 수가 10개인 단어 5,000개라면 글자 처리 횟수는 약 500,000회로, 쌍별 비교의 최대 250 million회에 비해 적습니다.
알고리즘
endWord가wordList에 없으면 0을 반환합니다.- 목록의 각 단어와
beginWord에 대해, 그 단어를 각L패턴의 버킷에 추가합니다. - 큐에
beginWord를 넣고 방문한 것으로 표시한 다음, 길이를 1로 설정합니다. - 큐를 한 레벨씩 처리합니다. 단어가
endWord이면 길이를 반환합니다. 그렇지 않으면 각 패턴에 대해 해당 버킷에 있는 방문하지 않은 모든 단어를 다음 레벨에 추가하고, 방문한 것으로 표시한 다음 버킷을 비웁니다. - 각 레벨이 끝난 후 길이에 1을 더합니다. 큐가 비면 0을 반환합니다.
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
size = len(beginWord)
# "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
buckets = defaultdict(list)
for word in set(wordList) | {beginWord}:
for i in range(size):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = deque([beginWord])
length = 1 # words in the sequence up to the current level
while queue:
for _ in range(len(queue)): # one level: every word at this distance
word = queue.popleft()
if word == endWord:
return length
for i in range(size):
pattern = word[:i] + "*" + word[i + 1:]
for neighbour in buckets[pattern]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
buckets[pattern] = [] # all of them are visited now: never scan it again
length += 1
return 0
함정과 경계 사례
대부분의 오답은 잘못된 것을 세거나 endWord에 관한 규칙을 지키지 않아 발생합니다.
- 변경 횟수 대신 단어 수를 반환하는 경우.
lead에서gold로 바꾸려면 변경 횟수는 3회이고 단어 수는 4개이므로, 정답은 4입니다. endWord가wordList에 있는지 확인하지 않는 경우. 두 번째 예제에서 탐색은dog에서 한 글자 떨어진 단어까지 도달하지만, 정답은 0입니다.- 깊이 우선 탐색을 사용하고 처음 찾은 사다리를 반환하는 경우. DFS는 한 분기를 끝까지 따라가므로, 처음 찾은 사다리는 긴 경우가 많습니다.
- 단어가 큐에 들어갈 때가 아니라 큐에서 나올 때 방문 처리하는 경우. 그러면 26개가 꽉 찬 버킷에 있는 단어가 최대 25번까지 큐에 들어가 큐가
n보다 훨씬 커질 수 있습니다. beginWord가wordList에도 있을 때 방문 처리하지 않는 경우. 그러면 탐색이 두 단계 뒤에 다시 해당 단어에 도달해 작업을 반복합니다. 시작부터 방문 처리하세요.- 최대 한 글자만 다른 단어를 확인하는 경우. 모든 단어는 자기 자신과 글자가 0개 다르므로 조건은 정확히 한 글자 차이여야 합니다.
- 사다리를 따라 재귀 호출하는 경우. 숨겨진 테스트에는 최단 사다리가 1,500개 단어로 이루어진 경우가 있으며, 일부 언어에서는 호출 스택이 넘칠 만큼 깊습니다. BFS에는 큐만 있으면 됩니다.
자주 묻는 질문4
왜 너비 우선 탐색은 가장 짧은 단어 사다리를 찾을까요?
BFS는 단어를 단계별로 탐색합니다. 먼저 시작 단어를 탐색하고, 그다음 한 번의 변경으로 도달할 수 있는 모든 단어를 탐색한 뒤, 두 번의 변경으로 도달할 수 있는 모든 단어를 탐색합니다. 단어는 그 단어에 도달할 수 있는 가장 이른 단계에서 처음 발견되므로, 그 거리는 가능한 최소 변경 횟수입니다. 모든 변경의 비용이 같기 때문에 가능한 방식입니다. 단계마다 비용이 다르다면 대신 다익스트라 알고리즘을 사용해야 합니다.
Word Ladder의 시간 복잡도는 얼마인가요?
와일드카드 버킷을 사용하면 패턴을 만들고 검색을 수행하는 데 n개의 길이 L인 단어에 대해 O(n × L²) 시간이 걸립니다. 각 단어에는 길이가 L인 패턴이 L개 있기 때문입니다. 모든 단어 쌍을 비교하면 O(n² × L)의 시간이 걸리고, 깊이 우선 탐색으로 모든 사다리를 시도하면 지수 시간이 걸립니다.
한 글자 차이인 단어는 어떻게 찾나요?
한 가지 방법은 위의 와일드카드 버킷을 사용하는 것입니다. 예를 들어 h*t와 같은 패턴을 공유하는 단어는 이웃입니다. 다른 방법은 단어의 각 위치를 26개 문자로 하나씩 바꾸고, 그 결과가 단어 해시 집합에 있는지 확인하는 것입니다. 단어마다 26 × L번 조회하고, 각 조회에서 L개의 문자를 해싱하므로 총 시간 복잡도는 O(n × 26 × L²)입니다. 두 방법 모두 전체 목록을 비교하는 것보다 효율적입니다.
양방향 BFS를 사용하면 Word Ladder를 더 빠르게 풀 수 있을까요?
네. beginWord와 endWord에서 동시에 검색하고, 항상 더 작은 쪽을 한 단계씩 확장하다가 새 단어가 반대쪽에서 이미 도달한 단어라면 중단합니다. 그러면 사다리의 단어 수는 양쪽에서 수행한 변경 횟수를 합한 값보다 하나 더 많습니다. 각 단어에 약 b개의 이웃이 있고 사다리에 d번의 변경이 필요하다면, 한 번의 검색은 약 b^d개의 단어를 방문할 수 있는 반면, 중간에서 만나는 두 번의 검색은 약 2 × b^(d/2)개의 단어를 방문합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def ladderLength(beginWord, endWord, wordList):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
기대값
4