프로그래머스 - Lv3 단어 변환

1. 문제

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

2. 고려할 사항

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

3. 풀이

• 최단 거리를 구하는 경우에 BFS 방식이 유용하므로 이를 사용하였다.
• 단어 목록 중 현재 단어와 알파벳 개수가 1개 다른 단어를 큐에 넣어준다.
  • 단어를 큐에 넣어주면서 step(단계)도 1 증가시킨다.
  • 큐에 넣어준 단어는 단어 목록에서 제거했는데, 중복 방문을 방지하기 위해서이다.
  • words의 길이가 50개 이하이기 때문에 그냥 단어 목록에서 제거하는 방법을 선택하였고, 수가 크게 늘어나면 방문 여부를 체크하는 방식을 사용할 수 있을 것 같다.
• 큐의 원소를 앞에서부터 꺼내면서 target 과 일치하는지 확인하고, 일치하는 경우에 step을 반환한다.

4. 풀이 코드

from collections import deque


def bfs(begin, target, words):
    size = len(begin)
    queue = deque([(begin, 0)])

    while queue:
        word, step = queue.popleft()

        if word == target:
            return step

        for compare_word, compare_step in words:
            diff = 0

            for i in range(size):
                if diff > 1:
                    break

                if word[i] != compare_word[i]:
                    diff += 1

            if diff == 1:
                queue.append((compare_word, step + 1))

    return 0


def solution(begin, target, words):
    words = list(zip(words, [0] * len(words)))
    return bfs(begin, target, words)

5. 배운 점

• 최단 거리는 역시 BFS 방식을 활용하자!