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

🧑🏻‍💻 문제링크

문제풀이

words가 ["hot", "dot", "dog", "lot", "log", "cog"] 라고 주어졌을 때 begin인 "hit"가 target인 "cog" 까지 최소 몇 단계에 거쳐 변환할 수 있는지 찾는 문제이다.

"hit"이 "cog"까지 변환하는 과정은 "hit" -> "hot" -> "dot" -> "dog" -> "cog"로 4단계로 거쳐갈 수 있다. 보통 BFS나 DFS와 같은 문제들은 그래프로 나타낼 수 있는 2차원 배열 문제에서 많이 볼 수 있는데 이 문제는 1차원 배열에서도 그래프 탐색 알고리즘을 사용할 수 있다는 것을 보여주는 문제인 것 같다.

구현 방법은 원래 알고있는 BFS 방식과 별 다를 바 없었지만 문제에서 요구되는 최소 단계를 어떻게 구현하는지가 중요하다. 최소 단계는 단어 리스트 안에 있는 단어를 확인해서 맞는 알파벳의 갯수가 (단어의 알파벳 수) - 1 이 되면 된다.

코드

def check(next_word, word):
    count = 0

    # zip 함수를 이용해서 단어의 알파벳이 맞는지 확인
    for a, b in zip(next_word, word):
        if a == b:
            count += 1

    # 한 단어만 바꿈 = 가장 짧은 변환 과정
    if count == len(word)-1:
        return True
    else:
        return False

def solution(begin, target, words):
    answer = 0

    if target not in words:
        return 0

    visited = [False] * len(words)
    queue = [begin]     # 큐 생성

    # BFS 방식
    while queue:
        next_word = queue.pop()

        if next_word == target:
            return answer

        for i in range(len(words)):
            if not visited[i]:
                if check(next_word, words[i]):
                    visited[i] = True
                    queue.append(words[i])

        answer += 1
    
    return answer

결과