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

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

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

 

dfs와 백트래킹으로 문제를 풀어봤다.

 

할 수 있는 모든 경우를 탐색하며 가장 최소로 바꾸며 타겟 단어까지 바꾼 횟수를 리턴해주었다.

 

 

 

import sys
 
cnt = 0
 
 
def solution(begin, target, words):
    answer = []
 
    # words 안에 타겟 단어가 없으면 애초에 변환 불가능
    if target not in words:
        return 0
 
    def dfs(start):
 
        global cnt
 
        # 바꾸지 못 할경우 가장 큰 값 반환
        if words.count("A") == len(words):
            return sys.maxsize
 
        for w in range(len(words)):
            for i in range(len(start)):
                # 한 글자를 제외하고 같으면 바꿀 수 있는 단어,
                # 단어는 무조건 3 이상이니까 1짜리 단어로 바꿔버리자
                if start[:i] + start[i + 1:] == words[w][:i] + words[w][i + 1:] and len(start) == len(words[w]):
                    if words[w] == target:
                        answer.append(cnt + 1)
                        return
                    a = start
                    start = words[w]
                    words[w] = 'A'
                    cnt += 1
                    dfs(start)
                    words[w] = start
                    start = a
                    cnt -= 1
 
    dfs(begin)
    return min(answer)