[Python/Programmers] 단어 변환

문제

1. 난이도: 프로그래머스 Lv.3

2. 문제 요약

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

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

3. 문제 핵심: BFS/DFS

내 코드

from collections import defaultdict

def solution(begin, target, words):
    if target not in words:
        return 0
    procDict = defaultdict(list)
    tmp = begin
    idx = -1
    for i in range(len(words)):
        for word in words:
            cnt = 0
            for j in range(len(tmp)):
                if tmp[j] != word[j]:
                    cnt +=1
            if cnt == 1:
                procDict[tmp].append(word)
            else:
                continue
        idx +=1 
        tmp = words[idx]

    cnt = 0
    stack = [begin]
    while stack:
        cnt +=1 
        tmp = stack[-1]
        if target in procDict[tmp]:
            return cnt
            break
        stack.append(procDict[tmp].pop())

        if cnt > len(words):
            return 0