[python] 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환

문제

해결

이 문제는 bfs로 풀면 간단한 문제다.
먼저 선입선출로 가장 빠른 길을 찾는 문제기 때문에 deque를 사용하여 구현한다.
그리고 한글자 차이인 단어를 찾아 차례대로 deque 에 넣고 바꾸고를 반복하며
원하는 단어가 나오는 가장 빠른 길을 찾는다.

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0
    
    queue = deque()
    queue.append([begin, 0])
    
    while queue:
        x, cnt = queue.popleft()
        if x == target:
            return cnt
        
        for i in range(0, len(words)):
            diff = 0
            word = words[i]
            for j in range(len(x)):
                if x[j] != word[j]:
                    diff += 1
            if diff == 1:
                queue.append([word, cnt+1])
        
    return 0