[프로그래머스] 단어 변환 - 파이썬(Python3)

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

프로그래머스

 

두 단어 begin, target 그리고 단어의 집합 words가 있다.

규칙을 지켜 begin -> target 의 가장 짧은 변환 과정을 찾는 문제이다.

규칙 1. 한 번에 한개의 알파벳만 바꿀 수 있다.

규칙 2. words에 있는 단어로만 변환할 수 있다.

 

제일 먼저 words에 target이 존재하는 지를 확인(규칙2)을 해야한다고 생각했다.

그 후에 한 개의 알파벳만 다른 단어로 변환(규칙1)될 때 +1씩 count 하며 진행했다.

변환한 단어와 target이 일치하면 count를 return 해 주면 된다.

 

from collections import deque

def solution(begin, target, words):
    
    if target not in words:
        return 0
    
    queue = deque()
    queue.append((begin,0))
    
    while queue:
        temp, cnt = queue.popleft()
        
        if temp == target:
            return cnt
        
        for i in range(len(words)):
            dif = 0
            word = words[i]
            for j in range(len(temp)):
                if temp[j]!=word[j]:
                    dif+=1
            if dif==1:
                queue.append((word,cnt+1))
    return 0

 

+ 문제 풀이를 안하다가 최근에 다시 시작했는데 그래서인지 편하다고 느껴지는 bfs로 풀게 된다..(bfs로 문제를 푸는 것도 능숙하진 않지만ㅎㅎ😥) 

dfs로 푸는 방법도 빠른 시일 내로 추가하고 싶다~!