[프로그래머스] 단어 변환 by 파이썬 (Python) : DFS

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

프로그래머스

 

난이도

LV 3

 

 

문제 설명

시작 단어 begin, 도착 단어 target이 주어지고 변환할 수 있는 단어의 배열 words가 주어진다.

변환할 수 있는 조건은 한번에 한 개의 알파벳만 바꿀 수 있고,

words안에 있는 단어로만 변경이 가능하다.

최소 몇단개에 걸쳐 begin의 단어를 target으로 변환 가능한지 Retrun해준다.

만약 변환할 수 없는 경우 0을 Retrun 해준다.

 

 

 

해결법

deque로 DFS를 구현해 해결하였다.

1. 단어와 몇번째 변환인지를 큐에 저장하고 words에서 변환할 수 있는 단어를 탐색해 큐에 저장한다.
2. 변환할 수 있느 단어인지 확인법은 for문으로 하나의 단어만 다른 경우를 세주었다.
3. 이 과정을 큐에 단어가 존재할 때 반복하다 단어가 target과 동일하면 총 단계의 수를 반환한다.
4. 만약 변환할 수 없는 경우에는 0을 반환한다.

 

 

코드

from collections import deque
def solution(begin, target, words):
    if target not in words:
        return 0

    q = deque()
    q.append([begin, 0])

    while q:
        s, idx = q.popleft()
        if s == target:
            return idx
        cnt = 0
        for i in range(len(words)):
            cnt = 0
            word = words[i]
            for j in range(len(s)):
                if s[j] != word[j]:
                    cnt += 1
            if cnt ==  1:
                q.append([word, idx + 1])
                
    return 0

 

---