단어 변환

문제

두 개의 단어 begin, target과 단어의 집합 words가 주어집니다.
아래 규칙을 이용해 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾습니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target이 "cog", words가 ["hot", "dot", "dog", "lot", "log", "cog"]라면 다음과 같이 4단계를 거쳐 변환할 수 있습니다.

hit -> hot -> dot -> dog -> cog

변환할 수 없는 경우에는 0을 반환합니다.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

사용 알고리즘

이 문제는 BFS를 사용해 해결할 수 있습니다.

begin에서 target까지 변환하는 최소 단계를 찾아야 하므로, 가능한 단어들을 하나씩 탐색하면서 가장 먼저 target에 도달하는 순간의 단계 수를 반환하면 됩니다.

단어 하나를 정점으로 보고, 한 글자만 다른 단어로 이동할 수 있다고 생각하면 그래프 탐색 문제가 됩니다. 이때 모든 이동 비용은 1로 같기 때문에 최단 거리를 구할 때 BFS가 적합합니다.

풀이 과정

1. target이 words 안에 없다면 변환할 수 없으므로 0을 반환합니다.
2. 큐에 시작 단어 begin과 현재 단계 0을 함께 넣습니다.
3. 큐에서 단어를 하나 꺼냅니다.
4. 현재 단어가 target이면 현재 단계 수를 반환합니다.
5. words의 모든 단어를 확인하면서 현재 단어와 한 글자만 다른 단어를 찾습니다.
6. 한 글자만 다르다면 다음 단계로 이동할 수 있으므로 큐에 넣습니다.
7. 같은 단어를 반복해서 방문하지 않도록 방문 처리를 합니다.
8. 끝까지 변환할 수 없다면 0을 반환합니다.

Python 풀이

from collections import deque


def solution(begin, target, words):
    if target not in words:
        return 0

    return bfs(begin, target, words)


# 최소 단계를 찾아야 하므로 bfs
def bfs(begin, target, words):
    queue = deque()
    queue.append([begin, 0])  # 시작 단어와 단계 0으로 초기화

    visited = set([begin])

    while queue:
        now, step = queue.popleft()

        if now == target:
            return step

        # 단어를 모두 체크하면서, 해당 단어가 변경될 수 있는지 체크
        for word in words:
            if word in visited:
                continue

            count = 0

            for i in range(len(now)):  # 단어의 길이만큼 반복하여
                if now[i] != word[i]:  # 단어의 알파벳을 한 개씩 체크하기
                    count += 1

            if count == 1:
                visited.add(word)
                queue.append([word, step + 1])

    return 0

코드 설명

if target not in words:
    return 0

target은 반드시 words에 있는 단어로만 변환할 수 있습니다.
따라서 target이 words에 없다면 더 탐색할 필요 없이 0을 반환합니다.

queue.append([begin, 0])

큐에는 현재 단어와 지금까지의 변환 단계를 함께 저장합니다.
처음에는 아직 변환하지 않았으므로 단계는 0입니다.

for word in words:
    count = 0

    for i in range(len(now)):
        if now[i] != word[i]:
            count += 1

현재 단어 now와 후보 단어 word를 한 글자씩 비교합니다.
서로 다른 글자의 개수가 1개라면 한 번의 변환으로 이동할 수 있는 단어입니다.

if count == 1:
    visited.add(word)
    queue.append([word, step + 1])

변환 가능한 단어라면 방문 처리한 뒤, 단계 수를 1 증가시켜 큐에 넣습니다.

시간복잡도

단어의 개수를 N, 단어의 길이를 L이라고 하겠습니다.

BFS에서 각 단어를 탐색할 때마다 words 전체를 확인합니다.
그리고 두 단어가 한 글자만 다른지 확인하기 위해 단어의 길이만큼 비교합니다.

따라서 시간복잡도는 다음과 같습니다.

O(N^2 * L)

제한사항에서 N은 최대 50, L은 최대 10이므로 충분히 효율적으로 해결할 수 있습니다.

공간복잡도

큐와 방문 집합에 최대 N개의 단어가 들어갈 수 있습니다.

O(N)

핵심 정리

• 최소 변환 단계를 찾아야 하므로 BFS를 사용한다.
• 현재 단어와 한 글자만 다른 단어만 다음 단어로 이동할 수 있다.
• target이 words에 없다면 변환할 수 없으므로 바로 0을 반환한다.
• 방문 처리를 해야 같은 단어를 반복 탐색하지 않는다.