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

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

프로그래머스

 
이 문제가 BFS를 이용하는 이유: "최소 단계 변환을 찾는 문제 -> 최단 경로 문제 -> BFS를 이용"

from collections import deque
def solution(begin, target, words):
    if target not in words:
        return 0
    q = deque()
    q.append([begin, 0])
    visited = [0]*len(words)
    def is_one_letter_diff(word1, word2):
        count = 0
        for a, b in zip(word1, word2):
            if a != b:
                count += 1
            if count > 1:
                return False
        return True if count == 1 else False
    def bfs():
        while q:
            word, steps = q.popleft()
            if word == target:
                return steps
            for i in range(len(words)):
                if not visited[i] and is_one_letter_diff(word, words[i]):
                    visited[i] = 1
                    q.append((words[i], steps+1))
        return 0
    return bfs()

백준: 단지 번호 붙이기,