[프로그래머스 2024/06/17] 단어 변환 - python

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

프로그래머스

 

1. 접근 방법

DFS 로 접근하기로 마음 먹고 문제에 다가가 보았다. 

 

또 다른 DFS로 넘어가는 조건은, 현재 단어와 words에 포함 되어 있는 단어의 차이가 1인 경우로 생각했다.

DFS 탈출 조건은 target과 현재 단어가 일치할 시, 로 고려했다.

 

또한, DFS 함수를 부르기 전에, 만약 target으로 하는 단어가 words에 포함이 되어 있지 않을 시엔, 바로 0을 return 해주었다.

 

 

---

deque(BFS) 를 사용하는 좋은 방법도 있었다. 이는 타겟 단어에 도착했을 때, 최소한의 변환 단계를 보장한다는 점에서 장점이 있다.

+ 이미 방문 완료한 단어를 다시 방문하지 않도록 하기 위해서는 set을 이용하여 visited 여부 또한 확인할 수 있다.

hit -> hot -> hit -> hot 을 반복하는 가지도 있지만, 경우를 만족한다면, return이 될 것이기 때문에 상관이 없음.

https://jie0025.tistory.com/486

[BFS][lv.3] 단어 변환 - 파이썬(Python)

 

 

2. 코드

def solution(begin, target, words):
    def DFS(begin, words, cnt):
        nonlocal min_step
        if begin == target:
            if cnt < min_step:
                min_step = cnt
                return

        for w in words:
            diff = 0
            for i in range(l):
                if w[i] != begin[i]:
                    diff += 1
            if diff == 1:
                words.remove(w)
                DFS(w, words, cnt + 1)
                words.append(w)
                
    l = len(begin)
    min_step = len(target) + 2
    
    if target not in words:
        return 0
    
    DFS(begin, words, 0)


    return min_step