[프로그래머스] 단어 변환

문제 링크 : programmers.co.kr/learn/courses/30/lessons/43163

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

재귀를 이용한 dfs로 해결하였는데, 최소 수행 횟수를 찾는 것이므로 bfs로 푸는 것이 더 좋을 것 같다는 생각을 했다. 

is_convertible은 인자로 들어온 2개의 문자열에 대해서 같은 위치에 있지만 다른 알파벳 개수를 계산하는데, 문제 조건에서는 다른 알파벳이 1개일 경우에만 단어 변환을 해줄 수 있으므로 다른 알파벳 개수가 1개이면 True, 1개가 아니면 False를 반환한다.

dfs에서는 리스트를 잘라서 인자로 넣어주므로 단어들의 리스트인 words의 길이가 0이면 재귀를 탈출하도록 하였다.

그리고 for문 내에서 리스트의 index를 삭제할건데, for문을 도는 리스트를 삭제하면 에러가 발생하므로 copy()를 통해 리스트의 복사본을 생성한다.

이후 문제 조건에 맞게 if문을 설정하고 방문한 element를 삭제한 후 다시 dfs의 인자로 넘겨주었다.

def is_convertible(word1, word2):
    # len(word1) == len(word2)
    num_diff_words = sum([True if ch1 != ch2 else False for ch1, ch2 in zip(word1, word2)])
    if num_diff_words == 1:
        return True
    else:
        return False
    

min_count = 99999
def dfs(begin, target, words, count):
    global min_count
    if len(words) == 0:
        return
    
    words_copy = words.copy()
    
    for i, word in enumerate(words):
        if is_convertible(begin, word):
            if word == target:
                if count < min_count:
                    min_count = count
                return
            
            del words_copy[i]
            dfs(word, target, words_copy, count+1)
            words_copy = words.copy()


def solution(begin, target, words):
    global min_count
    
    if target not in words:
        return 0
    
    dfs(begin, target, words, 1)
    
    return min_count