[프로그래머스 / 파이썬 풀이] 단어 변환

from collections import deque

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

bfs를 통한 풀이.

 

큐에 담긴 문자와 단어 배열에 있는 문자를 비교했을 때 서로 다른 문자의 개수를 확인한다.

만약 check가 1이라면 단어 하나가 다른 문자이기 때문에 큐에 넣고 계속 순회 시켜준다.

 

이후 target과 같은 문자를 찾으면 cnt 를 리턴해서 횟수를 찾는다.