참조

동빈나(유투브)-DFS

DFS

깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. DFS는 노드를 탐색할 대 주로 사용된다. 사실 스택을 사용하지 안항도 구현이 가능하다는 특징을 가지고 있다. 그러한 이유는 컴퓨터는 구조적으로 항상 스택의 원리를 사용하고 있기 때문이다.

DFS는 맨 처음에 시작 노드(1)를 스택에 삽입하면서 시작합니다. 또한 그와 동시에 시작 노드를 방문했다고 알리는 '방문 처리'를 해주도록 한다. 예를 들면 boolean visited[1(node)]=true라고 설정!

1. 스택의 최상단 노드를 확인한다.
2. 최상단 노드에서 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 뺀다.

이 알고리즘을 계속해서 반복 수행해주면 된다.

1번 노드(최상단) - 2번 노드 - 3번 노드

DFS는 깊이탐색이므로 3번노드에서 계속해서 연결되어있는 6번 노드 다음 7번노드가 스택에 삽입이된다. 이후에 이제 탐색할 곳이 없으니 후입선출(LIFO, last in, frist out)이므로 7번 노드가 나오고 다음 6번 노드가 나온다.

다음 2번 노드에서 위와 비슷하게 4번노드, 5번노드가 삽입이된다. 이후에 하나씩 다 노드들이 빠져나오게 된다.

따라서 경로는 1 - 2 - 3 - 6 - 7 - 4 - 5
가 된다.