[프로그래머스/Leve3] 단어 변환(Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제 접근

최단 거리를 구하는 문제는 BFS로 접근하는 것이 좋다.

DFS로 구하는 경우, 다시 순회할 지점을 잡기가 어렵기 때문이다.

그래프에서는 자식을 어떻게 설정할 것인가가 중요한 것 같다.

해당 문제는 단어 각 글자를 존재하는 모든 단어의 각 글자와 하나씩 바꾸면서 큐에 넣어줬다.

방문한 단어를 기록하며, 방문한 단어가 나올 시 처리가 되지 않아야 테스트 케이스 3번을 통과할 수 있다.

소스 코드

from typing import List
from collections import deque


def solution(begin: str, target: str, words: List[str]) -> int:
    if target not in words:
        return 0

    q = deque()
    visit = []

    q.append((begin, 0))

    while q:
        word, depth = q.popleft()
        if word in visit:
            continue
        visit.append(word)

        for i in range(len(word)):
            for w in words:
                child_word = list(word)
                child_word[i] = w[i]
                child_word = "".join(child_word)

                if child_word == word:
                    continue

                if child_word == target:
                    return depth + 1

                if child_word not in visit and child_word in words:
                    q.append((child_word, depth + 1))

    return 0