깊이/너비 우선 탐색(DFS/BFS) Level 3 단어 변환 - python (프로그래머스)

소스 코드

from collections import deque

def is_available_change(word, target):
    cnt = 0
    for a1, a2 in zip(word, target):
        if a1 != a2:
            cnt += 1
    return cnt == 1    

def solution(begin, target, words):
    
    global answer
    answer = 100000000000000000000
    
    if target not in words:
        return 0
    
    
    visited = [False] * len(words)
    def dfs(word, depth):
        global answer
        if word == target:
            answer = min(answer, depth)
            return
        
        for index, _ in enumerate(words):
            if visited[index] == True:
                continue
            if is_available_change(word, words[index]):
                visited[index] = True
                dfs(words[index], depth+1)
                visited[index] = False
    
    dfs(begin, 0)
        
    return answer

풀이

위 문제는 바꿀수 있는 단어인지 판단하는 is_available_change 함수를 잘못 작성해 놓고 계속 주구장창 다른게 문제 있나 확인하느라 애좀 먹었다. 

 

dfs의 탈출 조건으로는 target 단어로 변환이 완료된 경우 그때까지 몇번 변경되었는 지를 나타내는 depth를 answer에 저장해주었다. 하지만 그 과정에서 여러 가지의 경우가 나올 수 있으므로 min을 사용하여 최소 값만을 저장할 수 있도록 하였다.

 

여기서 키 포인트는 dfs 함수 내부에서 재귀를 돌릴때 한 단어 내에서 2가지 이상의 단어로 변경가능한 상황이 존재한다. 해당 상황을 위해 재귀를 끝내고 온 뒤 visited[index]를 False로 처리해주어 다음 상황에서 또 다른 단어로의 재귀가 일어날 수 있도록 해주어야 한다.