[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/43163
📌문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- 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 합니다.입출력 예
예제 #1)
begin : hit
target : cog
words : [hot, dot, dog, lot, log, cog]
return : 4예제 #2)
begin : hit
target : cog
words : [hot, dot, dog, lot, log]
return : 0입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.
💡문제 풀이
begin의 단어가 target이 될 때 까지 가장 짧은 변환 횟수를 찾는 문제
"한 번에 한 개의 알파벳만 바꿀 수 있다." 라는 조건은 한 개의 알파벳만 다르면 서로 변환할 수 있는 단어다.
즉, 서로 연결되어있다. 라고 생각하였고 최소 변환 횟수를 찾는 문제이기 때문에 BFS를 사용하였다.
step 1)
먼저, target 단어가 words 리스트에 없을 경우 0을 리턴한다.
step 2)
시작 단어(begin)을 담은 step에서 단어 하나를 뺀 다음 queue에 있는 단어들을 하나씩 빼내어 check 함수를 통해 서로 변환이 가능한 단어인지 확인한다.
이 때, queue에 있는 모든 단어를 한 바퀴 탐색하는 횟수가 곧, 변환 횟수(cnt)다.
check 함수에서는 모든 단어의 길이가 같다고 했으므로 인덱스를 이용해서 불일치하는 횟수가 몇 번인지 확인
→ 불일치하는 횟수가 1번이면 변환 가능 그렇지 않으면 변환 불가능!
step 3)
변환이 가능한 단어면
target 단어와 일치하는지 확인한다.
- 일치하면 cn아직 한 바퀴 탐색 전이므로 cnt + 1값을 return 한다.
- 일치하지 않으면 사용한 단어이므로 step에 담는다.
변환이 불가능하면 queue에 다시 담는다.
작성한 코드는 아래와 같다.
- queue : words 리스트를 담은 deque
- step : 사용한(변환한) 단어를 담는 deque
- cnt : 변환 횟수
- check 함수 : 두 단어가 변환이 가능한지(하나의 알파벳만 다른지) 판단
from collections import deque
def check(begin, compare):
count = 0
for i in range(len(begin)):
a, b = begin[i], compare[i]
if a != b:
count += 1
if count > 1:
return False
else:
return True
def solution(begin, target, words):
if target not in words: return 0
queue = deque(words)
step = deque([begin])
cnt = 0
while True:
for _ in range(len(step)):
start = step.popleft()
for i in range(len(queue)):
compare = queue.popleft()
if check(start, compare):
if compare == target:
return cnt + 1
step.append(compare)
else:
queue.append(compare)
cnt += 1