[Lv.3] 단어 변환

프로그래머스의 "단어 변환" 문제는 주어진 시작 단어(begin)를 목표 단어(target)로 변환하는 데 필요한 최소 단계를 찾는 문제입니다. 변환 규칙은 한 번에 하나의 알파벳만 변경할 수 있으며, 변경된 단어는 반드시 주어진 단어 목록(words)에 포함되어야 합니다.

문제 분석:

1. 단어의 구성 및 길이:
   모든 단어는 알파벳 소문자로 이루어져 있으며, 길이는 3자 이상 10자 이하로 동일합니다.

2. 변환 규칙:
   한 번에 하나의 알파벳만 변경 가능하며, 변경된 단어는 반드시 words에 존재해야 합니다.

3. 목표:
   begin에서 target으로의 변환에 필요한 최소 단계 수를 찾는 것입니다. 변환이 불가능한 경우 0을 반환합니다.

해결 방법:

이 문제는 그래프 탐색 알고리즘인 BFS(너비 우선 탐색)를 활용하여 해결할 수 있습니다. BFS는 최단 경로를 찾는 데 효과적이기 때문에, 각 단어를 노드로 간주하고, 한 글자만 다른 단어들 간의 변환을 간선으로 생각하여 탐색합니다.

구체적인 풀이 과정:

1. 초기 설정:
   words에 target이 없으면 변환이 불가능하므로 0을 반환합니다.
   begin을 시작점으로 하는 큐를 생성하고, 방문한 단어를 추적하기 위한 집합을 만듭니다.

2. BFS 탐색:
   큐에서 현재 단어와 변환 횟수를 추출합니다.
   현재 단어가 target과 같다면 변환 횟수를 반환합니다.
   아직 방문하지 않은, 한 글자만 다른 단어들을 찾아 큐에 추가하고 방문 처리합니다.

3. 변환 불가 시:
   큐를 모두 탐색한 후에도 target에 도달하지 못하면 0을 반환합니다.
   파이썬 코드 예시:

from collections import deque

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

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

    while queue:
        current_word, steps = queue.popleft()
        if current_word == target:
            return steps

        for i in range(word_len):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + char + current_word[i+1:]
                if next_word in words and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))

    return 0

• deque를 사용하여 큐를 구현하고, visited 집합을 통해 이미 방문한 단어를 추적합니다.
• 현재 단어에서 한 글자씩 변경하여 새로운 단어를 생성하고, 이 단어가 words에 있으며 방문하지 않았다면 큐에 추가합니다.
• 큐에서 target 단어를 찾으면 현재까지의 변환 횟수를 반환합니다.
• 모든 경우를 탐색한 후에도 target에 도달하지 못하면 0을 반환합니다.