[프로그래머스] 단어 변환 (파이썬)

📕 문제

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

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

 

💡 풀이법

1. dfs 재귀를 이용해서 단어를 변환해간다. dfs의 n은 변환한 횟수를 뜻한다.

2. 사용한 단어를 체크해주는 visited 리스트를 만들어준다.

3. answer는 최소 변환 횟수이다. 만약 n이 answer와 같거나 넘어가면 재귀를 멈춘다.

4. word가 target과 같아지면 answer과 n을 비교해서 더 작은 값을 answer에 넣는다.

5. words의 단어들과 word를 비교하면서 다른 부분이 1개인 단어일때만 재귀 함수를 실행한다. 사용한 단어는 visited에 체크를 해주고 재귀 함수가 끝나면 방문 체크를 해제해 준다.

def solution(begin, target, words):
    def dfs(word, n):
        nonlocal answer

        if n >= answer:
            return
        
        if word == target:
            answer = min(answer, n)

        for i in range(len(words)):
            cnt = 0
            if not visited[i]:
                for a,b in zip(word, words[i]):
                    if a != b:
                        cnt += 1
                        if cnt > 1:
                            break
                else:
                    visited[i] = 1
                    dfs(words[i], n+1)
                    visited[i] = 0

    answer = float('inf')
    if target not in words:
        return 0

    visited = [0] * len(words)
    dfs(begin, 0)

    return answer