[DFS] 단어 변환 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3 

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

 

Fact Finding

---

• DFS 문제를 통해 최소 변환 횟수를 찾기

Algorithm Flow

---

• recursion을 통한 DFS 구현 후 가장 최소의 경우를 final_result에 저장

여기서 주의해야 할 부분이 바로 global 변수의 활용이다!!

 

구현 코드

# 반례
# hit
# cog
# cog cot dot dog dut
#global a
#a = 0
def check(begin, target) : ## 한 개의 알파벳만 바꾸기 위한 check 함수
    check_count = 0
    for i in range(len(target)) : 
        if begin[i] != target[i] : 
            check_count += 1
    if check_count == 1 : 
        return True
    return False

def problem(now, targt, words, final_result=100000000, result = 0): 
    global a
    a = 0
    if now == targt : ## Base case
        #global a
        a = 1
        return result
    for i in words : 
        if i != now : 
            if check(now, i) : ## 전환 가능한 경우
                index = words.index(i)
                del words[index] ## 해당 단어 제외
                result = problem(i, targt,words) + 1 ## Depth First Search
                final_result = min(result, final_result) ## 가장 최저 경로를 저장
                words.insert(index, i) ## recursion이 끝난 뒤로 다시 추가
    if a == 0 : 
        return 0
    return final_result
    

def solution(begin, target, words):
    answer = 0
    if target in words : 
        answer = problem(begin, target, words)
    return answer