DepthFirstSearch1 [C++] 깊이 우선 탐색(DFS : Depth First Search) 이번 시간에는 깊이 우선 탐색에 대해 알아보도록 하겠다. 깊이 우선 탐색(DFS)는 탐색을 할 때 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. 이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용된다. 이전에 배웠던 너비 우선 탐색에서는 큐를 사용하였고, 이번 깊이 우선 탐색에서는 스택을 사용한다. 컴퓨터는 항상 스택의 원리를 사용하기 때문에 사실 스택을 사용하지 않아도 된다. 맨 처음에 시작 노드(Start Node)를 스택에 넣어주고 시작 노드를 방문했음을 알리는 방문 표시를 한다. 그 다음에는 다음의 알고리즘을 반복한다. 1. 스택의 최상단 노드를 확인한다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드.. 2020. 5. 7. 이전 1 다음