[프로그래머스 lv3] 단어 변환

문제 보기

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3 

프로그래머스

 

소스 코드

from collections import deque
def solution(begin, target, words):
    answer = 0
    
    q = deque()
    q.append((begin, 0)) # (단어, 깊이)
    depth_list = [0] * len(words)
    
    while q:
        word, cnt = q.popleft()
        if word == target:
            answer = cnt
            break
        for i in range(len(words)):
            tmp_cnt = 0
            if depth_list[i] == 0:  # 아직 확인하지 않은 단어일 경우
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        tmp_cnt += 1
                if tmp_cnt == 1:  # 다른 글자 수가 1개일 때
                    q.append((words[i], cnt + 1))
                    depth_list[i] = 1
                            
    return answer

 

참고 및 출처

https://naa0.tistory.com/153

[BFS / 최상급] 단어변환 (프로그래머스, Python, Level3)