프로그래머스
- 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- words에 있는 단어로만 변환할 수 있습니다.
- 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 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 |
접근 방식
- 스택은 나중에 들어온 값을 pop하기 때문에 바로 이전의 단어와 다음 단어가 관련이 있음(알파벳 한개 차이)
- 그러나 큐(덱)은 처음 들어온 값을 pop하기 때문에
[dot, lot]에서 dot을 popleft하고 넣은 dog
즉 [lot, dog]에서 이후 lot에 대해 수행하기 때문에 각 단어에 대한 단계 즉 depth가 필요함.
코드
스택을 이용한 DFS
def solution(begin, target, words):
if target not in words:
return 0
s = [begin]
visited = [0]*len(words)
ans = 0
while s:
value = s.pop()
if value == target:
return ans
for word in words:
if visited[words.index(word)] == 0:
cnt = 0
for a, b in zip(value, word):
if a != b:
cnt += 1
if cnt == 1:
s.append(word)
visited[words.index(word)] = 1
ans += 1
큐(덱)을 이용한 BFS
from collections import deque
def func(word, w):
cnt = 0
for a, b in zip(word, w):
if a != b:
cnt += 1
if cnt == 1:
return True
return False
def solution(begin, target, words):
if target not in words:
return 0
visited = []
q = deque()
q.append((begin, 0))
visited.append(begin)
ans = 0
while q:
w, d = q.popleft()
if w == target:
return d
for word in words:
if word not in visited and func(word, w):
q.append((word, d+1))
visited.append(word)
큐에 넣을 때 단어와 depth를 쌍으로 넣는다.
depth를 기록할 리스트를 따로 만들어도 됨.
