[programmers/py] 단어 변환

단어 변환

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

문제 설명

• 두 개의 단어 begin, target과 단어의 집합 words가 있습니다
• begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
• 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
• words에 있는 단어로만 변환할 수 있습니다.

문제 풀이

• 최소 횟수를 구하는 문제라 BFS 문제

from collections import deque

def solution(begin, target, words):
    
    if target not in words :
        return 0
    
    return BFS(begin, target, words)

def BFS(begin, target, words):
    queue = deque()
    queue.append([begin, 0])
    
    while queue:
        n, i = queue.popleft()
        
        if n == target :
            return i
        
        # 단어의 1가 다르면 queue에 추가
        for word in words :
            count = 0
            for idx in range(len(word)) :
                if word[idx] != n[idx] :
                    count +=1
            
            if count == 1:
                queue.append([word, i+1])