프로그래머스 : 단어 변환

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

코딩테스트 연습 - 단어 변환

 

해결 방법 : BFS

• 단어 개수가 많지 않기 때문에 완전 탐색 가능.
  • target word로의 최소 변환 횟수를 구하는 것이기 때문에 BFS를 사용하면 더 효율적이다.
    
    • DFS는 모든 경우를 탐색 → 최솟값 반환
    • BFS는 target word가 최소로 나오면 해당 위치 count가 최솟값

 

from collections import deque

def solution(begin, target, words):
    path = []
    Q = deque([(begin, 0)])
    while Q:
        cur_word, count = Q.popleft()
        if cur_word == target: return count
        
        for word in words: # 단어가 하나만 다르고, 이미 거쳐온 단어가 아닐 시, 탐색
            if len([1 for i, j in zip(cur_word, word) if i == j]) == len(word) - 1 and word not in path:
                Q.append((word, count + 1))
                path.append(word)
        
    return 0