[프로그래머스] 단어변환 lv 3 (python)

최단 단어 변환 수를 찾는 것이니 BFS로 풀자는 것만 알면 어려운 문제는 아니라고 생각한다..

 

단어 최대 길이도 10이고 배열 길이도 max가 50이라 이중for문이 들어가도 시간초과가 안뜬다.

 

from collections import deque

def diff(word, target):
    cnt = 0
    for i in range(len(word)):
        if word[i] != target[i]:
            cnt += 1
    return cnt
    
def solution(begin, target, words):
    if target not in words:
        return 0
    visited = [0 for i in range(len(words))]
    deq = deque([(begin, 0)])

    while deq:
        now, cnt= deq.popleft()
        
        if now == target:
            return cnt
        
        for i, word in enumerate(words):
            if visited[i] == 0 and diff(word, now) == 1:
                visited[i] = 1
                deq.append((word, cnt+1))
    
    return 0