문제

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

나의 코드

"""

"""

from collections import deque

def diff(a, b):
    diff_cnt = 0

    for i in range(len(a)):
        if a[i] != b[i]:
            diff_cnt += 1

    return diff_cnt

def solution(begin, target, words):
    n = len(words)
    visited = [False] * n
    answer = 1e9

    def bfs():
        q = deque([(begin, 0)])

        while q:
            word, cnt = q.popleft()

            if word == target:
                return cnt

            for i in range(n):
                diff_cnt = 0
                if not visited[i]:
                    diff_cnt = diff(word, words[i])

                if diff_cnt == 1:
                    visited[i] = True
                    q.append((words[i], cnt + 1))

    if target not in words:
        return 0

    answer = min(answer, bfs())
    return answer
    
    

설명

BFS 문제

참고 자료