문제
문제 설명
두 개의 단어 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 합니다.
입출력 예
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 안에 없기 때문에 변환할 수 없습니다.
문제 해결 접근
-
카테고리와 같이 dfs/bfs 로 접근해서 풀 수 있을 것이라고 생각했다.
-
일종의 이 단어들은 그래프로 표현될 수 있다고 생각했다. 각 단어가 노드라고 한다면, 한글자만 변환할 수 있다면 엣지가 연결 되고, begin -> target 까지의 최단 경로를 찾으면 된다고 생각했다. 아래 그림이 예제1을 그림으로 나타낸 것이다.
-
그러나 일반적인 그래프 문제처럼 그래프가 구축되어서 주어지는 것이 아니기 때문에, "한글자만 빼고 같은 단어" 즉, 엣지가 연결되어 있는지 확인하는 알고리즘을 어떻게 구축해야 할까 생각했다. 효율적으로 하기는 어려울 것 같았고, 입출력의 크기와 단어의 길이가 길지 않기 때문에 이중 for 문을 확인하기로 했다.
-
최단 경로이다보니 bfs가 조금 더 효율적일 것이라고 판단하였고, 큐에 넣어서 확인하고자 하였다. 내가 아직 bfs에 익숙하지 않다보니 큐에 어떻게 넣어야지 최단 경로를 같이 판단할 수 있지? 🤔 를 고민했던 것 같다.
-
그리고 target을 반환할 수 없는 경우를 어떻게 정의하지? 라고 생각했는데 보면 문제에 적혀져 있었다. target이 words 안에 없으면 반환할 수 없다고 판단하면 된다.
코드 구현
from collections import deque
def solution(begin, target, words):
## target을 만들 수 없으면 반환하기
if target not in words:
return 0
visited = [0]*(len(words))
queue = deque([(begin, 0)]) ## bfs 시작, 단어와 현재까지의 경로를 큐에 같이 넣어주기
while queue:
current = queue.popleft()
if current[0] == target:
break
for w_idx, w in enumerate(words):
## 이미 방문 했던 단어는 넘어가기 / 자기 자신도 넘어가게 됨
if visited[w_idx] == 1 :
continue
## current 에서 한 글자 바꿔서 변경 가능한 애들은 큐에 추가하기
correct = 0
wrong = 0
for iidx, i in enumerate(list(w)):
if i == current[0][iidx]:
correct += 1
else:
wrong += 1
if correct == len(current[0])-1 and wrong == 1:
queue.append((w, current[1]+1))
visited[w_idx] = 1
return current[1]- visited 리스트를 만들어서 방문했던 단어이면 넘어갈 수 있도록 하였다.
- 큐에 집어넣을 때, 각 level을 뒤에 같이 넣게 하였다. begin으로부터 한 글자가 바뀐 것이면 1, 그 다음 단계이면 2와 같이 현재 몇 번째 단계까지 왔는지를 큐에서 확인할 수 있도록 하였다.
- 반복문은 큐가 있는 동안 진행되도록 하였고, 현재 단어가 target과 같으면 그 때도 바로 반환하도록 하였다. (반환하지 않을 경우 반복문이 더 돌면서 answer가 틀리게 되는 경우가 있었다.)
느낀 점
- 큐에 넣어서 확인하는 bfs 문제는 문제 조건에 따라서 1) 큐에 어떤 요소를 함께 넣어서 확인할 것이고 (단어의 인덱스나 현재까지의 최단거리나...), 2) 종료 조건을 어떻게 설정할 것인지가 가장 중요한 것 같다.
- 그래프나 주어지거나 맵에서 최단 경로 찾는 것 이외에도 이런 문제 유형이 자주 나오는 것 같으니 잘 익혀둬야 겠다.
