단어변환 43163
🕷 문제 설명
두 개의 단어 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 합니다.
🫓 풀이
최근 재귀가 아닌 stack, queue 를 활용해서 DFS, BFS 를 구현하는게 자주 보이는 것 같다.
먼저 해당 문제는 현재의 단어(now) 와 1개의 글자 차이가 나는 단어를 찾고 변환하는 과정을 반복해야한다.
그래서 DFS 를 생각했는데, 여기저기 찾아보다보니 최소 횟수 를 구하는 문제들에는 BFS 를 주로 쓴다고 하는 것을 보았다 . . . . . . .
따라서 맨 처음을 제외하고 queue 의 front 를 now, depth 로 두고 한글자 차이가 나는 단어들을 계속 queue에 넣어주었다.
탐색하면서 queue 가 비게되면 다 탐색했거나, 1글자 차이나는 단어가 없는 경우이기 때문에 0을 반환하게 했다.
🌯 코드
def solution(begin, target, words):
depth = 0
now = begin
que = []
visit = [0 for _ in range(len(words))]
if target not in words: return 0
while(True):
if len(que) > 0:
now, depth = que[0]
del que[0]
if (now == target): return depth
for i in range(len(words)):
if (visit[i] == 0):
s = 0
for j in range(len(words[i])):
s += (words[i][j] != now[j])
if s == 1:
que.append([words[i], depth + 1])
visit[i] = 1
if (len(que) == 0): return 0
return depth⚾️ 어려웠던 점
- 문제 이해가 어려웠다. 예시만 보면
words배열에서 순서대로 탐색해야하는 줄 알았다 . . << 역시 독해가 제일 어렵다. queue를 활용한 BFS 공부(stack을 통한 DFS 도. .) 를 좀 더 해서 익숙해질 필요가 있다.
이얀조다!