프로그래머스 - 단어 변환

간만에 풀어본 알고리즘 문제

사실 오랜만에 풀었는데 다른 서치없이 원큐에 맞춰서 기분좋아서 올리는 포스팅

 

begin -> target으로 단어를 최소 몇 단계로 변환 가능한지 / 혹은 불가능한지 확인하는 문제이고

단어는 words 사전에 등록되어 있는 단어로만 바꿀 수 있으며 단계 당 한 글자 씩만 바꿀 수 있다.

 

예시만 보더라도 이미 변환을 거쳤던 단어로 다시 가게 될 경우가 존재하므로 거쳤는 단어인지 확인 필요하며

DFS로 구현할 경우 일단 가능하지 않은 경우로 너무 깊게 빠질 수가 있으므로 BFS로 구현

 

해답

from collections import deque

def check_diff(a, b):
    cnt = 0
    for c_a, c_b in zip(a, b):
        if c_a != c_b:
            cnt += 1
            if cnt > 1:
                return False
            
    return True

def solution(begin, target, words):
    answer = 0
    
    is_valid = [1 for w in words]
    
    q = deque()
    q.append(begin)
    
    while q:
        for i in range(len(q)):
            tmp = q.popleft()   
            
            if tmp == target:
                return answer
    
            for i, word in enumerate(words):
                if is_valid[i] and check_diff(tmp, word):
                    is_valid[i] = 0
                    q.append(word)
            
        answer += 1
        
    return 0