[프로그래머스] : lv.3 - 단어 변환 (파이썬)

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

프로그래머스

 

BFS 문제 

 

문제

코드

from collections import deque


def bfs(queue, words, target):
    while queue:
        now, counts = queue.popleft()
        
        if target == now: 
            return counts
        
        for i in range(len(words)):
            cnt = 0
            for a, b in zip(now, words[i]):
                if a != b: cnt += 1
                if cnt > 1: break
            if cnt == 1: 
                queue.append((words[i], counts + 1))
                words[i] = "" # 이미 count한 문자열의 경우 다시 계산하지 않도록 빈 문자열로 변경 
                
        # print(queue)
    return 0
                
    

def solution(begin, target, words):
    answer = 0
    queue = deque()
    queue.append((begin,0))
    
    answer = bfs(queue, words, target)
    
    return answer

 

이미 queue에 넣어 계산한 문자열의 경우 다시 계산하지 않도록 빈 문자열로 변경하는 부분을 추가해주었다.

 

*참고문헌

https://jie0025.tistory.com/486