프로그래머스 - 단어변환(DFS) - python

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

def is_one_diff(a, b):
    diff_cnt = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            diff_cnt += 1

    return diff_cnt == 1

    return False

def recursive_dfs(begin, target, words, tmps):
    tmps.append(begin)
    
    if begin == target:
        return 1
    for word in words:
        if is_one_diff(begin, word) and word not in tmps:
            return 1 + recursive_dfs(word, target, words, tmps)

    return 0
    
def dfs(begin, target, words):
    
    if target not in words:
        return 0

    for word in words:
        if is_one_diff(begin, word):
            return recursive_dfs(word, target, words, [])

    return 0

def solution(begin, target, words):
    return dfs(begin, target, words)  
    

Recursive_dfs(word, target, words, [])가 어떻게 바로 최솟값인 3이 나오는가?
-> hit -> hot -> dot ->lot ->log
.............................-> dog -> cog(4)번째에서
.............................................. -> log
얘를 가장 먼저 발견하니까 begin == target이네!하고 가장 먼저 종료 시키는거 같음 recursive자체가 알아서 is_onediff에서 1만 나오는 모든 경우의 수를 모두 살펴보는듯

이러므로 한번 사용한 단어는 절대 재사용하면 안됨 -> 그래서 tmps라는 배열을 따로 만들어서 방문여부를 체크함

회고

일단 dfs와 bfs를 쓰는건 맞는데(어떤 과정이나 경로를 찾는 문제는 dfs/bfs문제인듯) 어떤 한 조건이 들어가있는(한번에 한 개의 알파벳만 바뀔수있다) 그런 문제이다. 이 조건에 대해서 사람들마다 따로 빼서 함수로 구현하든지 아니면 함수 안에 따로 메소드를 구현하든지 했는데 따로 빼서 함수로 구현하기