[프로그래머스 Lv.3] 단어 변환

프로그래머스

from collections import deque

def solution(begin, target, words):
    if target not in words: # words 안에 없다면 0 반환
        return 0
    
    def canExchange(arr_a,arr_b): # 바꿀 수 있는 알파벳인지 확인
        diff = 0
        for i in range(len(arr_a)):
            if arr_a[i] != arr_b[i]:
                diff += 1
        if diff == 1:
            return True
        else:
            return False
    
    def bfs():
        queue = deque([(begin,0)])
        
        while queue:
            current, depth = queue.popleft()
            
            if current == target:
                return depth
            
            for word in words:
                if canExchange(current,word):
                    queue.append((word,depth+1))    
        return 0
    
    return bfs()

이번 문제는 단어의 알파벳을 하나만 바꿀 수 있다는 가정하에 begin에서 target으로 바꾸기 위한 최소 변환 횟수를 구하는 문제이다.

 

최소 횟수를 구한다는 멘트를 보자마자 BFS 알고리즘을 떠올렸고, 알파벳을 하나만 바꿀 수 있다는 조건을 위해 수정 여부를 확인하는 canExchange 함수를 구현하여 간단하게 풀이하였다 :)