문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
<코드>
from collections import deque
def is_one_letter_diff(word1, word2):# 두 단어가 한 글자만 다른지 확인하는 함수
diff_count = sum(a != b for a, b in zip(word1, word2))
return diff_count == 1
def solution(begin, target, words):
if target not in words:
return 0
words = set(words) # 집합으로 변환하여 중복 방지 및 빠른 검색
queue = deque([(begin, 0)]) # (현재 단어, 단계 수)
visited = set([begin])
while queue:
current_word, steps = queue.popleft()
if current_word == target:
return steps
for word in words:
if word not in visited and is_one_letter_diff(current_word, word):
visited.add(word)
queue.append((word, steps + 1))
return 0
<풀이과정>
- is_one_letter_diff(word1, word2):
- 두 단어가 한 글자만 다른지 확인하는 함수
- solution(begin, target, words):
- target이 words에 포함되지 않는 경우, 변환이 불가능하므로 0을 반환
- BFS를 위한 큐를 초기화하고, 시작 단어와 단계 수를 큐에 추가
- 큐에서 단어를 하나씩 꺼내면서 변환 가능한 단어를 찾고, 변환 단계 수를 업데이트하며 큐에 추가
- 목표 단어에 도달하면 단계 수를 반환
- 모든 단어를 탐색한 후에도 목표 단어에 도달하지 못하면 0을 반환
'2024 코딩테스트 스터디' 카테고리의 다른 글
[12주_6일차] 프로그래머스-여행경로(Python) (0) | 2024.08.25 |
---|---|
[12주_5일차] 프로그래머스-아이템 줍기(Python) (0) | 2024.08.25 |
[12주_3일차] 프로그래머스-게임 맵 최단거리(Python) (0) | 2024.08.22 |
[12주_2일차] 프로그래머스-네트워크(Python) (0) | 2024.08.21 |
[12주_1일차] 프로그래머스-타겟 넘버(Python) (0) | 2024.08.20 |