문제
두 개의 단어 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 함수를 작성해주세요.
입출력 예
begin target words return
hit cog [hot, dot, dog, lot, log, cog] 4
hit cog [hot, dot, dog, lot, log] 0
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.
풀이
단순하게 생각하여 begin 단어가 target 단어까지 바뀌려면 몇 단계를 거쳐야하는가를 묻는 질문이다.
단어는 한 번에 한 글자만 바꿀 수 있다.
그래서 현재 단어와 한 글자만 다른 단어를 찾기 위해
현 단어와 비교할 단어를 한 글자씩 비교해 다른 글자의 수가 총 1개인 경우 반환한다.
여기서 파이썬 generator와 yield 개념이 나오는데,
함수 A에서 차례대로 반환할 yield 값들을 정의해 놓으면 함수 A는 iterate 가능한 객체, generator가 된다.
그래서 generator 'get_adjacent()'에서 조건에 맞는 원소들을 조회하고 dist에 기록하고 queue에 넣어준다. 더 이상 조건을 충족하는 요소가 없어서 queue가 비면 dist에서 target에 기록된 단계를 반환한다.
from collections import deque
def get_adjacent(current, words):
for word in words:
count = 0
for c, w in zip(current, word):
if c != w:
count += 1
if count == 1:
yield word
def solution(begin, target, words):
dist = {begin: 0}
queue = deque([begin])
while queue:
current = queue.popleft()
for next_word in get_adjacent(current, words):
if next_word not in dist:
dist[next_word] = dist[current] + 1
queue.append(next_word)
return dist.get(target, 0)Thought:
최근 탐색 알고리듬을 보고있는데 처음 봤을 때, '방문한다' 등의 표현도 감이 안왔다.
그래서 직접 문제와 풀이들을 보고 공부하고있다.
이 풀이는 프로그래머스의 python3 최상단에 있는 것을 가져왔다.
zip이나 yield 등의 파이썬 기능들의 활용이 잘 된 풀이 같다.
