[programmers/python] 단어 변환 – 두 가지 BFS 풀이 비교

- url : https://school.programmers.co.kr/learn/courses/30/lessons/43163

 

주어진 단어 집합을 이용하여 begin 단어를 target 단어로 변환할 수 있는 최소 단계 수를 구하는 문제이다. 이때, 단어를 변환하는 규칙은 다음과 같다:

1. 한 번에 한 글자만 바꿀 수 있다.
2. 바꾼 결과는 반드시 words 리스트에 존재해야 한다.

예를 들어 "hit" → "hot" → "dot" → "dog" → "cog"처럼 4단계에 걸쳐 변환할 수 있다면, 4를 반환한다. 단, 변환이 불가능한 경우에는 0을 반환해야 한다.

---

문제 조건 요약

• 모든 단어는 길이가 동일하며, 알파벳 소문자로만 구성된다.
• words 리스트는 중복이 없으며, 길이는 최대 50이다.
• 변환 과정에서 항상 words 내 단어만 사용할 수 있다.
• begin과 target이 같은 경우는 주어지지 않는다.

---

접근 1. 그래프를 미리 만들어 BFS 수행하기 (인접 리스트 방식)

핵심 아이디어

단어마다 알파벳을 하나씩 바꿔보며, words 집합에 존재하는 단어만 간선으로 연결하는 그래프를 미리 구성한다. 이후 일반적인 BFS로 최단 경로를 탐색하면 된다.

구현

from collections import deque, defaultdict

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

    graph = defaultdict(set)
    alpha = [chr(i) for i in range(ord('a'), ord('z') + 1)]
    _set = set(words) | {begin}

    for word in _set:
        for i in range(len(word)):
            for ch in alpha:
                if ch != word[i]:
                    cand = word[:i] + ch + word[i+1:]
                    if cand in _set:
                        graph[word].add(cand)

    queue = deque([(begin, 0)])
    visited = set()

    while queue:
        word, depth = queue.popleft()
        if word == target:
            return depth
        if word in visited:
            continue
        visited.add(word)
        for neighbor in graph[word]:
            if neighbor not in visited:
                queue.append((neighbor, depth + 1))

    return 0

시간 복잡도

• 그래프 구성: O(N × L × 26) (N: 단어 수, L: 단어 길이)
• BFS 탐색: O(N)

장점

• 탐색 시 매번 인접 단어를 찾는 비용이 O(1)이다.
• 여러 쿼리(begin, target)에 대응하기 유리하다.

---

접근 2. 탐색 중에 인접 단어를 비교하며 찾기 (실시간 비교 방식)

핵심 아이디어

단어를 탐색하면서 매번 현재 단어와 words의 각 단어를 비교하여 한 글자만 다른 단어를 찾는다. 이 방식은 그래프를 미리 만들지 않아도 된다.

구현

from collections import deque

def get_adjacent(current, words):
    for word in words:
        if len(current) != len(word):
            continue
        diff = sum(c1 != c2 for c1, c2 in zip(current, word))
        if diff == 1:
            yield word

def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()
        for neighbor in get_adjacent(current, words):
            if neighbor not in dist:
                dist[neighbor] = dist[current] + 1
                queue.append(neighbor)

    return dist.get(target, 0)

시간 복잡도

• BFS 중 비교: O(N × L) per node
• 전체 탐색 시간: O(N² × L)

장점

• 구현이 단순하고 직관적이다.
• 입력이 작을 경우 성능 차이가 거의 없다.

---

입출력 예시

solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])  # → 4
solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"])        # → 0