BFS 연습 - 단어변환(프로그래머스)

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

✔︎ 더 알아봐야 할 점

- DFS에서의 백트래킹하듯이 BFS 에서도 적당히 가지치기 하면 좋겠다 싶다.

- 그런데 이를 위해서는 모든 큐의 원소에서 기억하고 가지고 다녀야 할 정보? 메모리?에 부담이 늘어나는 것이 아닐까?

- 더 좋은 방법으로 BFS에서 가지치는 방법은 어떤 것이 있을까?

import collections

def solution(begin, target, words):
    n = len(begin)

    que = collections.deque()
    que.append((begin, 0))

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

        # 타겟 발견하면 cnt 로 탐색한 레벨을 리턴
        if word == target:
            return cnt

        # 탐색을 허락할 수 있는 최대 레벨(깊이/cnt)는 words 에 포함된 친구들 개수이므로
        # 여기까지 왔는데도 답을 못 찾았다면,
        # 소모적인 탐색 그만두게 하기
        if cnt >= len(words):
            break

        # 후보 단어들 중에 다른 글자수가 1이라면 변환 가능한 단어이므로,
        # 변환 횟수인 cnt 를 +=1 하여 다음의 가능성 있는 변환을 위해 큐에 넣어 줌.
        for candidate in words:
            diff = 0
            for i in range(n):
                if word[i] != candidate[i]:
                    diff += 1
            if diff == 1:
                que.append((candidate, cnt+1))

    # 답을 찾지 못하고 while 종료시 0 리턴
    return 0