[Programmers_Python] 단어 변환

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

프로그래머스

이 문제는 BFS방식을 이용해서 풀 수 있다. 처음에 몇번 째에 정답에 도착하는 지를 잘못 지정해서 계속 틀렸던 것 같다.

문제에서 주어진 예시를 그래프로 나타내면 위와 같은 방식이 된다.

from collections import deque

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

    q = deque()
    q.append([begin, 0])

    while q:
        x, cnt = q.popleft()

        if x == target:
            return cnt 

        for i in range(len(words)):
            diff = 0
            word = words[i]
            for j in range(len(x)):
                if x[j] != word[j]:
                    diff += 1
            if diff == 1: # 한 알파벳만 달라야 변환 가능하다.
                q.append([word, cnt + 1]) # 변환 가능한 단어만 q에 넣는다.
    return 0

큐에 넣을 때, 몇번 걸쳐서 그 단어에 도달했는지를 나타내는 cnt 값도 같이 넣어주는 방식으로 진행을 해야 내가 한 틀린 방식을 해결할 수 있는 것 같다. 그러고 특정 단어에서 1개의 알파벳만 다른 단어를 찾고 그 단어를 큐에 넣어준다. 이런 방식을 q에 아무것도 없을 때까지 while문을 반복하고 target이 나오면 그때의 cnt값이 정답이고 정답이 안나오면 target에 도달할 수 없다는 것이기에 0을 return하도록 한다.