[Level 3] 단어 변환

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

코딩테스트 연습 - 단어 변환

---

접근

dfs를 통해 현재 단어에서 1개의 글자만 다를 때 해당 단어로 다음 탐색을 진행한다. 진행하다가 target 단어가 되었을 때 지금까지의 depth가 답이된다.

 

구현

- 먼저 answer에는 words의 길이에 + 1로 하여 찾지 못했을 때 0을 출력하도록 한다.

- picked에 지금까지 선택한 단어들을 추가한다.

- dfs를 진행하면서 현재 단어와 탐색하는 단어에서 다른 문자의 개수가 1이고 지금까지 선택을 안했을 때 다음 dfs를 진행한다.

- 현재 단어가 target과 같을 때는 dpeth를 answer에 저장한다.

def solution(begin, target, words):
    answer = len(words) + 1
    
    def dfs(cur_word, target, picked, words, depth):
        nonlocal answer
        if cur_word == target:
            answer = depth
            return
        
        for word in words:
            count = 0
            if word in picked:
                continue
            for i in range(len(word)):
                if word[i] != cur_word[i]:
                    count += 1
                if count > 1:
                    break
            if count == 1:
                picked.append(word)
                dfs(word, target, picked, words, depth+1)
                picked.pop()
                
    picked = [begin, ]
    dfs(begin, target, picked, words, 0)
    if answer == len(words) + 1:
        answer = 0
    return answer