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

result = list()


def solution(begin, target, words):
    global result
    answer = 0
    if target not in words:
        return 0
    elif target == begin:
        return 0

    visited = [False] * len(words)
    dfs(begin, target, words, visited, answer)
    return min(result)


def dfs(begin, target, words, visited, answer):
    global result
    if begin == target:
        return result.append(answer)

    change = list()

    for word in words:  #바꿀수 있는 단어 찾기
        count = 0
        for i in range(len(word)):
            if begin[i] != word[i]:
                count += 1
        if count == 1:
            change.append(word)

    for word in change:
        if not visited[words.index(word)]: #방문한 단어가 아니면
            visited[words.index(word)] = True #방문처리
            dfs(word, target, words, visited, answer + 1) #재귀
            visited[words.index(word)] = False #방문처리한거 되돌리기
solution("hit", "cog", a)

 

dfs 백트래킹을 사용하여 문제를 해결하였다.

 

먼저 begin 단어에서 words중 바꿀수 있는 단어를 찾는다.

찾은 단어들을 방문했는지 확인한다.

방문을 하지 않았으면 dfs(재귀)를 돌린다.

방문했던 단어를 다시 False로 바꾼다.