단어 변환

Problem Link
https://school.programmers.co.kr/learn/courses/30/lessons/43163

✅ Problem Summary

두 개의 단어 begin, target과 단어의 집합 words가 주어질 때, begin을 target으로 변환하는 최소 단계 수를 구하는 문제

• 한 번에 한 개의 알파벳만 바꿀 수 있음
• words에 있는 단어로만 변환할 수 있음
• 모든 단어의 길이는 같으며, 중복되는 단어는 없음
• 변환할 수 없는 경우에는 0를 return

---

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search)

그림 출처: Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과

from collections import deque
def solution(begin, target, words):
    if target not in words:
        return 0

    queue = deque([(0, begin)])
    while queue:
        depth, tempWord = queue.popleft()
        if tempWord == target:
            return depth

        for w in words:
            diffChar = 0
            for i in range(len(w)):
                if tempWord[i] != w[i]:
                    diffChar += 1
            if diffChar == 1:
                queue.append((depth + 1, w))
    return 0

📌 코드 구현 설명

• 현재 단어 tempWord가 target 단어와 같은지 확인한다.
• 만약 tempWord가 target 단어와 같지 않다면 word에서 바꿀 수 있는 문자를 탐색한다.
  • 한 번에 한 문자만 바꿀 수 있기 때문에, tempWord에서 하나의 문자만 다른 문자를 찾는다.
• tempWord가 target와 같아질 때 까지 반복하며, 만약 바꿀 수 없다면 0을 return 한다.

---