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 합니다.
입출력 예
입력 | begin: "hit", target: "cog", words: ["hot", "dot", "dog", "lot", "log"]
출력 | 0
풀이
begin에서 target으로 변환하는 과정은 한 단계에 한 개의 알파벳만 바꿀 수 있고 그 과정이 가장 짧은 방법을 찾는 문제이기 때문에 BFS로 풀었다.
위의 그림처럼 words 리스트에서 begin과 한 글자만 다른 단어들을 모두 확인하고 다음 단계로 넘어가고 또 그 단어와 한 글자만 다른 단어들을 모두 확인하는 것을 반복하면 답을 구할 수 있다.
현재 단어에서 한 글자가 다른 단어들을 count와 함께 모두 큐에 추가하고 그 큐에 있는 모든 단어들을 target과 비교해서 같으면 count를 리턴하게끔 구현했다.
포스팅하면서 생각난건데 방문 처리를 통해 더 효율적인 코드를 만들 수 있을 것 같다는 생각이 든다. 지금 코드는 한 글자가 다른 모든 단어를 다 순회하는데 이미 앞에서 확인한 단어는 다시 확인할 필요가 없으니까 더 효율적이지 않을까 ?.? 나중에 코드 수정하게 되면 추가해야겠다.
코드
from collections import deque
def solution(begin, target, words):
if target not in words:
return 0
q = deque()
q.append((begin, 0))
while q:
word, count = q.popleft()
if word == target:
return count
for w in words:
diff = 0
for i in range(len(word)):
if word[i] != w[i]:
diff += 1
if diff == 1:
q.append((w, count + 1))
return 0