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

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

프로그래머스

---

1. 풀이

• 가장 먼저 두 단어의 서로 다른 철자 개수를 세는 함수를 만들자

현재 단어 current에서 다른 단어로 변환하기 위해선 current와 다른 단어는 딱 1개만 서로 다른 철자를 가져야 한다. 따라서 변환할 수 있는 단어를 찾기 위해 해당 함수가 필요하다.

 

 

• 재귀를 돌려서 계속 words 단어 내 단어를 탐색하자

재귀 함수 종료 조건은 현재 단어 current와 target이 같을 때이다.

서로 같지 않다면, words로 반복문을 돌린다. 현재 원소 (단어)가 current와 철자가 1개만 다르면 해당 단어로 변환하고, 다시 재귀 함수를 호출한다. 이때 파라미터로 words를 넘기는데, 똑같은 단어로 다시 변환하면 안 되므로 words에서 현재 변환된 단어는 제외해서 넘긴다.

 

 

 

2. 정답 코드

global answer
answer = 10 ** 6

def solution(begin, target, words):
    find_next(begin, target, set(words), 0)
    return 0 if answer == 10 ** 6 else answer

def find_next(current, target, words, step):
    global answer
    if current == target:
        answer = min(answer, step)
        return
    
    for i, word in enumerate(words):
        if count_diff(current, word) == 1:
            find_next(word, target, words - {word}, step + 1)

def count_diff(word1, word2):
    return len([1 for x, y in zip(word1, word2) if x != y])