프로그래머스 - 고득점 kit - DFS/BFS - 단어변환 (Level3)
📖Problems
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
`1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- 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”]c | 4 |
| “hit” | “cog” | [“hot”, “dot”, “dog”, “lot”, “log”] | 0 |
입출력 예 설명
예제 #1문제에 나온 예와 같습니다.
예제 #2target인 “cog”는 words 안에 없기 때문에 변환할 수 없습니다.
🔍Institution
- begin =
hit - words =
[hot, dot, dog, lot, log, cog] - target =
cog
주어진 파라미터들을 토대로 그래프를 그려보면 아래 그림과 같다. 
또한 백트래킹이란, 시작 노드를 설정을 한 후, 이웃노드를 방문하는 것이다. 이는 모든 노드를 다 방문할 때까지 반복한다.
대표적으로 DFS와 BFS가 있다. 이 둘의 차이점은 이름에서부터 쉽게 느껴지지만, 어떻게 활용하느냐가 헷갈려서 찾아봤다.
- DFS : 재귀적, 모든 경우의 수, 순열과 조합
- BFS : 최소/최단길이, 깊이
이 문제에서는 최소값을 구하는 것이므로, BFS를 활용했다. DFS는 stack이나 recursion으로 풀이하고 BFS는 queue로 풀이할 수 있다.
BFS에 대해 chatGPT에게 물어봤다. 
BFS stands for Breadth-First Search, which is a graph traversal algorithm used to explore all the nodes in a graph.
In BFS, we start at a designated node (often referred to as the root node) and visit all its neighbors first. Then, we move to the next level of neighbors, visiting all their neighbors, and so on, until we have visited all nodes reachable from the root.
BFS is often implemented using a queue data structure, where we enqueue the root node and then repeatedly dequeue the next node and enqueue its neighbors until the queue is empty. BFS is commonly used in algorithms for pathfinding, network traversal, and other graph-based problems.
BFS는 그래프의 모든 노드를 탐색하는 데 사용되는 그래프 순회 알고리즘인 너비 우선 검색의 약자입니다.
BFS에서는 지정된 노드(종종 루트 노드라고 함)에서 시작하여 모든 인접 노드를 먼저 방문합니다. 그런 다음 루트에서 연결할 수 있는 모든 노드를 방문할 때까지 다음 단계의 이웃으로 이동하여 모든 이웃을 방문하는 등의 작업을 수행합니다.
BFS는 종종 큐 데이터 구조를 사용하여 구현되는데, 여기서 루트 노드를 큐에 넣은 다음 다음 노드를 반복적으로 디큐하고 큐가 비워질 때까지 인접 노드를 큐에 넣는다. BFS는 일반적으로 경로 찾기, 네트워크 트래버설 및 기타 그래프 기반 문제를 위한 알고리즘에 사용된다.
🔍Approach
queue에 초기 노드값을 집어넣어준다.queue에서 단계를 거친다는 것은 곧 그래프의 깊이를 의미한다. 따라서 begin과 인덱스값을 함께 넣어준다. (queue.append([begin, 0])- 시작하기 앞서,
words리스트에target값이 없다면 바로 0을 return한다. - 한번 방문한 노드는 방문하지 않도록 하기 위해
visited리스트를words리스트 길이만큼 False로 초기화한다. queue를 popleft()하여 값은temp에 인덱스는cnt에 넣어준다.cnt는 그래프의 깊이를 의미하기도 하지만, 몇 단계를 거쳤는지도 의미한다.temp값이target값과 같다면 바로cnt를 return한다. 이때 BFS이고, 맨 끝까지 보는 것이 아니기 때문에 바로 return하더라도 최솟값을 return하게 된다.- 이중for문으로 단어 안에서
words리스트 길이만큼 아래 과정을 반복한다.temp와words리스트 안에 있는 값을 철자 하나씩 비교한다. 만약 다른 게 있다면diff에+1해준다.- 한 개의 알파벳만 바꿀 수 있다는 것은 곧, 한 개의 값만 달라야 한다는 조건이므로, 단어의 차이, 즉
diff가 1일 때,queue에 값을 append하고 다음 단계로 넘어간다. - 이때, 재방문을 방지하기 위해, 방문하지 않았을 경우에만 위의 과정을 수행한다. (
visited[i] == False)
queue가 다 빌 때까지 위 4 ~ 6 과정을 반복한다. (즉, 모든 노드를 방문할 때까지 반복한다)이때 종료조건은 위 5번과 같이, target값을 만나게 되었을 때 종료한다.
🚩My submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque
def solution(begin, target, words):
if target not in words:
return 0
queue = deque()
queue.append([begin, 0])
visited = [False] * len(words)
while queue:
temp, cnt = queue.popleft()
if temp == target:
return cnt
for i in range(0, len(words)):
diff = 0
word = words[i] # hot
if visited[i] == False:
for j in range(len(temp)):
if temp[j] != word[j]: # [h, i, t] vs [h, o, t]
diff += 1
if diff == 1:
queue.append([words[i], cnt + 1])
visited[i] = True
return 0
🚩Others submission
[BFS / 최상급] 단어변환 (프로그래머스, Python, Level3)
[프로그래머스] 단어 변환(BFS,DFS,백트래킹) / C++
💡TIL
사실 처음에 감을 잡기 쉽지 않았다. 이걸 어떻게 하나하나 비교하지? 했던 것 같다. 이번주 DFS/BFS 스터디 시간에 계속 헤매었는데 이번에 준비하면서 DFS, BFS를 언제 쓰는지도 알게 되었고, queue에 대해서도, 조건 설정하는 것에 대해서도 조금 더 잘 알게 된 것 같다.
역시.. 그림을 그려봐야 방향이 잡히는 것 같다.
또, 이렇게 깊이를 이용할 때는 queue에 인덱스도 같이 저장해주어야 한다.
다음번에는 꼭 혼자 힘으로 풀어보고 싶다.