문제 개요
단어들을 담은 리스트(dictionary)와 두 개의 문자열 start, end가 주어진다고 가정해 봅시다. 우리는 start에서 end까지 도달해야 하며, 이때 한 번에 한 글자씩만 변경할 수 있습니다. 또한 변경 과정에서 만들어지는 모든 단어는 반드시 사전에 포함되어 있어야 합니다. 단어의 대소문자는 구분됩니다. 목표는 start에서 end에 도달하기 위해 필요한 최소 단계 수를 찾는 것이며, 도달이 불가능한 경우에는 -1을 반환해야 합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
dictionary = ["may", "ray", "rat"]
start = "rat"
end = "may"
이 경우 출력은 3입니다. ["rat", "ray", "may"]라는 경로를 따라가면 세 번의 글자 변경만으로 목표 단어에 도달할 수 있기 때문입니다.
접근 방법: 너비 우선 탐색(BFS)
이 문제는 그래프 탐색 관점에서 바라볼 수 있습니다. 각 단어를 노드로 생각하고, 한 글자만 다른 단어들 사이를 간선으로 연결하면 'start에서 end까지의 최단 경로'를 찾는 문제가 됩니다. 가중치가 없는 그래프의 최단 경로는 BFS(너비 우선 탐색)로 효율적으로 구할 수 있습니다.
알고리즘 단계
- 사전을 집합(set)으로 변환하여 중복을 제거하고 조회 속도를 높입니다.
- 덱(deque)에 (start, 1) 쌍을 삽입합니다. 여기서 1은 현재까지의 단계 수를 의미합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- 큐의 왼쪽에서 (word, distance)를 꺼냅니다.
- word가 end와 같으면 distance를 반환합니다.
- word의 각 자리 i에 대해, 알파벳 소문자 26개를 하나씩 대입해 새 단어 next_word를 만듭니다.
- next_word가 사전에 존재하면 사전에서 제거하고, (next_word, distance + 1)을 큐의 오른쪽에 삽입합니다.
- 반복이 끝날 때까지 end에 도달하지 못하면 -1을 반환합니다.
이미 사용한 단어를 사전에서 즉시 제거하는 것이 핵심입니다. 이렇게 하면 같은 단어를 중복 방문하는 것을 막아 무한 루프를 방지하고 탐색 범위를 줄일 수 있습니다.
Python 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
from collections import deque
class Solution:
def solve(self, dictionary, start, end):
dictionary = set(dictionary)
q = deque([(start, 1)])
while q:
word, distance = q.popleft()
if word == end:
return distance
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + c + word[i + 1:]
if next_word in dictionary:
dictionary.remove(next_word)
q.append((next_word, distance + 1))
return -1
ob = Solution()
dictionary = ["may", "ray", "rat"]
start = "rat"
end = "may"
print(ob.solve(dictionary, start, end))
입력
["may", "ray", "rat"], "rat", "may"
출력
3
복잡도 분석
단어의 길이를 L, 사전에 있는 단어 수를 N이라 할 때, 각 단어마다 L개의 자리에 26개의 알파벳을 대입하므로 시간 복잡도는 대략 O(N × L × 26 × L)입니다. 공간 복잡도는 큐와 집합 저장에 O(N × L)입니다.