Word Ladder

Q: Word Ladder의 시간 복잡도는 무엇인가요?

와일드카드 버킷을 사용하면 길이가 L 인 n 개의 단어에 대해 O(n × L²) 의 시간 복잡도가 듭니다. 각 단어에는 L 개의 글자로 이루어진 패턴이 L 개 있습니다. 모든 단어 쌍을 비교하면 O(n² × L) 의 비용이 들고, 깊이 우선 탐색으로 모든 사다리를 시도하면 지수 시간이 걸립니다.

어려움그래프 큐

+10

두 단어 beginWord와 endWord, 그리고 단어 목록 wordList가 주어집니다. 사다리는 beginWord로 시작하고 endWord로 끝나며, 각 단어에서 다음 단어로 넘어갈 때 정확히 한 글자만 바뀝니다. beginWord 이후의 모든 단어는 wordList에 포함되어야 하므로 endWord는 목록에 있어야 하지만, beginWord는 목록에 없어도 됩니다.

양 끝 단어를 모두 세어 가장 짧은 사다리에 포함된 단어의 개수를 반환하고, 사다리가 없으면 0을 반환합니다.

함수

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: 사다리의 첫 번째 단어
endWordstring: 사다리가 도달해야 하는 단어
wordListstring-array: 이후의 모든 단계가 가져와야 하는 단어들
반환값integer: 가장 짧은 사다리를 구성하는 단어의 수이며, 그런 사다리가 없으면 0

제약 조건

1 ≤ beginWord.length ≤ 10
endWord와 wordList의 모든 단어는 beginWord와 길이가 같습니다.
1 ≤ wordList.length ≤ 5000
모든 단어는 소문자 영어 문자만 포함합니다.
beginWord != endWord
wordList에 있는 단어는 모두 서로 다릅니다. beginWord는 그중 하나일 수도 있고 아닐 수도 있습니다.

예제

입력: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
출력: 4
설명: lead와 gold는 세 글자가 다르므로 단어 사다리에는 최소 4개의 단어가 필요하며, lead, load, goad, gold는 4개입니다. lend와 lewd는 막다른 길입니다.

입력: 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도 목록에 있지만, 시작 단어는 한 번만 계산됩니다.

후속 질문

길이 대신, 가장 짧은 사다리 하나를 단어 순서대로 반환할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

단어를 그래프의 노드로 보고, 한 글자 차이가 나는 단어 사이에 간선이 있다고 생각하세요. 모든 간선의 비용이 같으므로 너비 우선 탐색으로 가장 짧은 사다리를 찾을 수 있습니다. 어려운 부분은 간선을 빠르게 찾는 것입니다. 아래에서 n은 단어의 개수이고 L은 단어의 길이입니다.

깊이 우선 탐색으로 모든 사다리를 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

현재 단어에서 한 글자만 다른 사용되지 않은 단어를 모두 시도하고, endWord에 도달할 때까지 길이를 유지하며 더 깊이 탐색하세요. 경로상의 단어는 사용한 것으로 표시하고, 되돌아나올 때는 사용 해제하세요. best개의 단어로 이루어진 사다리가 존재하면 best-1개의 단어로 이루어진 경로는 더 이상 확장하지 마세요.

이 방법은 단어를 반복하지 않는 모든 사다리를 시도하며, 최단 사다리에서는 단어가 반복되지 않습니다. 같은 단어가 두 번 나타나는 사이의 부분을 잘라내면 길이가 짧아지기 때문입니다.

aaa, baa부터 zaa까지의 26개 단어는 모두 한 글자만 다르며, 약 4 × 10^26가지 순서로 배열할 수 있습니다. endWord에 도달할 수 없다면 가지치기가 작동하지 않아 탐색은 이 모든 경우를 시도합니다.

알고리즘

beginWord가 목록에 있으면 사용됨으로 표시하고, best를 0으로 설정합니다.
search(word, length): endWord에 도달하면 length가 best보다 작을 경우 best를 length로 설정하고 반환합니다. best가 설정되어 있고 length + 1 ≥ best이면 반환합니다.
그렇지 않으면, 사용되지 않은 단어 중 한 글자만 다른 각 단어를 사용됨으로 표시하고 search(next, length + 1)을 호출한 다음 사용됨 표시를 해제합니다.
search(beginWord, 1)을 호출한 뒤 best를 반환합니다.

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

너비 우선 탐색, 모든 쌍 비교하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

큐는 거리 순서대로 단어를 탐색합니다. 거리 d인 모든 단어가 거리 d + 1인 단어보다 먼저 큐에서 빠져나옵니다. 따라서 어떤 단어에 거리 d로 처음 도달하면, 그보다 가까운 모든 단어를 이미 탐색한 상태이며, 그 단어로 가는 더 짧은 사다리가 있다면 더 일찍 도달했을 것입니다. 단어는 큐에 들어가는 순간 거리가 확정되므로 그때 방문한 것으로 표시하고, endWord가 처음 나타났을 때의 거리가 답입니다.

이 버전은 목록의 모든 단어와 비교하여 단어의 이웃을 찾고, 두 번째 차이가 발견되면 비교를 멈춥니다. 복잡도는 O(n² × L)이며, 단어가 5,000개일 때 단어 비교가 최대 2,500만 번 발생합니다.

알고리즘

endWord가 wordList에 없으면 0을 반환합니다.
beginWord를 길이 1로 큐에 넣고, 목록에 있으면 방문한 것으로 표시합니다.
다음 단어를 꺼내 방문하지 않은 모든 단어와 비교합니다. 한 글자만 다른 각 단어에 대해, 해당 단어가 endWord이면 길이 + 1을 반환하고, 그렇지 않으면 방문한 것으로 표시한 뒤 길이 + 1로 큐에 넣습니다.
큐가 비면 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번 해시 조회하여 찾습니다.

첫 번째 예시에서 l*ad에는 load가 있고, le*d에는 lend와 lewd가 있으므로 레벨 2에는 이 세 단어가 있습니다. 그런 다음 *oad에서 goad를 찾고, go*d에서 레벨 4의 gold를 찾습니다.

버킷을 한 번 훑으면 그 안의 모든 단어에 도달하므로 버킷을 비웁니다. 26개 단어가 있는 *aa 버킷은 26번이 아니라 한 번만 훑습니다. 시간 및 공간 비용은 O(n × L²)이며, 길이가 10글자인 단어 5,000개를 처리할 때 글자 연산은 약 500,000회입니다.

알고리즘

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

함정과 경계 사례

단어 수 대신 변경 횟수를 세는 것. lead에서 gold까지는 3번 변경하지만 단어는 4개이므로 답은 4입니다.
endWord가 wordList에 있는지 확인하지 않는 것. 두 번째 예제에서는 cog가 dog와 한 글자만 다른데도 답은 0입니다.
단어가 큐에서 나갈 때 방문한 것으로 표시하는 것. 그러면 *aa 버킷에 있는 단어가 최대 25번 합류할 수 있고, 큐는 n보다 훨씬 커집니다.
변환 사다리를 따라 재귀하는 것. 최단 변환 사다리가 수천 개의 단어로 이루어질 수도 있어 호출 스택이 넘칠 수 있습니다.

자주 묻는 질문3

Word Ladder의 시간 복잡도는 무엇인가요?

와일드카드 버킷을 사용하면 길이가 L인 n개의 단어에 대해 O(n × L²)의 시간 복잡도가 듭니다. 각 단어에는 L개의 글자로 이루어진 패턴이 L개 있습니다. 모든 단어 쌍을 비교하면 O(n² × L)의 비용이 들고, 깊이 우선 탐색으로 모든 사다리를 시도하면 지수 시간이 걸립니다.

한 글자만 다른 단어를 어떻게 찾을까요?

와일드카드 버킷은 한 가지 방법입니다. 다른 방법은 각 위치를 26개 문자 각각으로 바꾸고, 그 결과를 단어 해시 집합에서 조회하는 것입니다. 단어당 26 × L번 조회하며, 각 조회는 L개의 문자로 이루어집니다. 총 시간 복잡도는 O(n × 26 × L²)입니다. 두 방법 모두 목록을 한 번 순회하는 것보다 효율적입니다.

양방향 BFS를 사용하면 Word Ladder를 더 빠르게 풀 수 있을까요?

네. 양쪽 끝에서 동시에 검색하면서 항상 더 작은 쪽을 한 단계씩 확장하고, 두 쪽이 만나는 순간 멈추세요. 단어당 이웃이 약 b개이고 변경 횟수가 d회라면, 한 번의 검색은 약 b^d개의 단어를 확인할 수 있습니다. 양쪽 끝에서 검색해 중간에서 만나면 약 2 × b^(d/2)개의 단어를 확인합니다.

def ladderLength(beginWord, endWord, wordList):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

예상 출력

Word Ladder

함수

제약 조건

예제

힌트

풀이

깊이 우선 탐색으로 모든 사다리를 시도해 보세요

너비 우선 탐색, 모든 쌍 비교하기

와일드카드 버킷을 사용한 너비 우선 탐색

함정과 경계 사례

자주 묻는 질문3

비슷한 문제