설명

프로그래머스의 단어 변환 문제다.

단어를 한 번에 한 글자만 바꿀 수 있다고 할 때 주어진 단어 리스트를 활용하여 시작 단어에서 목표 단어까지 변환할 수 있는지를 탐색하는 문제다.

중복되는 단어는 없으며 모든 단어의 글자는 동일하기 때문에 한 글자씩 변환하며 그래프 탐색으로 해결할 수 있다.

풀이

일단 한 글자씩만 바꿔야 하기 때문에 현재 단어에서 주어진 단어들을 비교하며 단 한 글자만 다른지 확인하는 로직만 잘 구현해주면 된다.

시작 글자는 바꿀 수 있는 단어에 들어있지 않을 수도 있기 때문에 시작 글자와 주어진 모든 글자를 비교해보면서 한 글자만 다를 경우 재귀 탐색하는 식으로 구현할 수 있다.

이를 기반으로 구현한 코드는 다음과 같다.

def solution(begin, target, words):
    # 목표 단어가 바꿀 수 있는 단어에 들어있지 않을 경우 예외 처리.
    if target not in words:
        return 0
    
    # 이미 한 글자 바꿔서 도달했던 단어를 기억.
    # 한번 바꿔서 도달한 단어라면 다시 올 필요가 없음.
    used = [False] * len(words)
    # 내부 함수에서 갱신을 위해 리스트로 구현.
    answer = [9999]
    
    # 단 한 글자만 다른지 확인하는 함수.
    def check_changeable_word(word1, word2):
        count = 0
        for index, char1 in enumerate(word1):
            if char1 != word2[index]:
                count += 1
                
            if count > 1:
                return False
        
        return True
    
    # 재귀 호출로 탐색.
    def find_shortest_solution(used_word_indexes, current_word_index, level):
        # 현재 단어가 목표 단어라면 몇 번이나 거쳐왔는지 갱신.
        if words[current_word_index] == target:
            answer[0] = min(answer[0], level)
            return
        
        # 매번 모든 단어들을 비교하며 탐색.
        for index, word in enumerate(words):
            # 한번 탐색했던 단어는 다시 탐색하지 않음.
            if index in used_word_indexes:
                continue
            
            # 현재 단어와 후보 단어를 비교.
            # 한 글자만 다르다면 해당 단어로 탐색.
            current_word = words[current_word_index]
            if check_changeable_word(current_word, word):
                find_shortest_solution(used_word_indexes.union({index}), index, level+1)
    
    # 탐색 시작.
    for index, word in enumerate(words):
        if check_changeable_word(begin, word):
            find_shortest_solution({index}, index, 1)
        
    return answer[0]

후기

전형적인 DFS/BFS 탐색 문제라고 할 수 있다.