[프로그래머스][Python] 단어 변환 - 코팩

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

프로그래머스

문제

주어진 문자열의 문자로 변환할 수 있는지 확인하는 문제이다. 

문자마다 경유하는 루트가 다르기에 cost변수를 따로 추가해서 경유한 단어의 개수를 기록해주었다.

BFS 알고리즘을 이용하기에 가장 먼저 target에 도달하는 루트가 최단 루트이다.

from collections import deque

def solution(begin, target, words):
    answer = 0
    queue = deque([[begin, 0]])
    n = len(begin)
    visited = [False] * len(words)
    while queue:
        c, cost = queue.popleft()
        
        if c == target:
            return cost
        
        for i in range(len(words)):
            if visited[i] == False:            
                count = 0
                for j in range(n):
                    if words[i][j] == c[j]:
                        count += 1
                        
                if count == n-1:
                    queue.append([words[i], cost+1])
                    visited[i] = True
                
    return 0