[2021/07/22][짤막한 이야기 - 깊이 우선 탐색]

[2021/07/22][짤막한 이야기 - 깊이 우선 탐색]
“깊이 우선 탐색(Depth First Search, DFS)”이란 어떠한 그룹을 전체적으로 탐색할 때 깊이를 우선으로 하여 탐색하는 기법이다.
일반적으로 “트리(Tree)”를 탐색할 때에 우선시 하는 탐색 방법을 의미한다.
트리는 자료구조 중 하나로 다음에 소개할 주제이기도 하다.
트리의 깊이를 우선하여 탐색한다는 것은 갈림길이 나왔을 때 아래로 먼저 진행한다는 의미이기도 하다.
그리고 이것은 이전에 언급하였던 “우수법”과 동일한 알고리즘이다.
동굴에서 벽에 손을 짚고 걷는다는 것은 갈림길이 나올때마다 안으로 더 깊이 들어간다는 의미이기도 하다.
따라서 갈림길에서 잘못된 방향을 선택할 경우 동굴 출구로의 최단 거리를 구하는 것은 어려워진다.
이것이 깊이 우선 탐색이 최단 경로 탐색을 최단 시간에 파악하기 어려운 이유이다.
[관련된 짤막한 이야기 - 동적 분석 & 정적 분석[2021/02/18]]
#이야기 #루니프 #알고리즘 #깊이우선탐색 #트리 #우수법 #최단경로

[2021/07/22][Short Story - Depth First Search]
“Depth First Search” is a technique for searching with depth-first when searching for a group as a whole.
In general, it refers to a search method that is prioritized when searching for a “Tree”.
A tree is one of the data structures and is also a topic to be introduced next.
Prioritizing the depth of the tree search also means that when a fork is found, it proceeds down first.
And this is the same algorithm as the “Right-Hand Method” mentioned earlier.
Walking with your hand against the wall in a cave also means going deeper into each fork in the road.
Therefore, if you choose the wrong direction at the fork, it becomes difficult to find the shortest path to the cave exit.
This is the reason that depth-first search is difficult to identify the shortest path search in the shortest time.
[Related Short Story - Dynamic Analysis & Static Analysis[2021/02/18]]
#Story #LootNiP #Algorithm #DepthFirstSearch #Tree #RightHandMethod #ShortestPath