[Algorithm] 깊이 우선 탐색(DFS, 그래프 탐색) 알고리즘

알고리즘에 대한 이해 !

알고리즘 문제 풀이에서 DFS, BFS를 많이 사용했었는데 이제야 알고리즘 정리를 하게됬네요 !

깊이 우선 탐색(DFS)란 DFS(Depth-First Search)는 그래프의 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘 입니다 !

DFS는 주로 반복문을 활용하거나 재귀문을 통하여 구현합니다.

 

DFS의 탐색 과정

DFS의 기본 탐색 과정은 특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 것입니다.

탐색하는 과정은 다음과 같습니다 !

1. 현재 노드를 방문한 것으로 표시한다.
2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
3. 더 이상  방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking)한다.
4. 모든 정점을 방문할 때까지 프로세스를 반복한다.

DFS의 탐색 방법을 이해하기 위해 아래의 예시를 봅시다 !

위와 같은 트리 구조가 있을 때 아래의 과정을 거치게 됩니다.

가장 먼저 루트 노드인 A를 방문하고, 스택에 추가합니다.

이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가합니다.

(C노드를 먼저 방문해도 됩니다. 순서는 상관 없습니다.)

이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가합니다.

다시 스택의 top 부분에 있는 B의 인접 노드인 E를 방문하고, 스택에 E노드를 추가합니다.

이후 스택의 top 부분에 있는 E의 인접 노드를 방문해야 하는데, E의 인접노드가 없으므로 스택에서 E노드를 제거합니다.

이후 스택의 top 부분에 있는 B의 인접 노드를 방문해야 하는데, B의 인접 노드는 이미 모두 방문했으므로 스택에서 B노드를 제거합니다.

이후 스택의 top 부분에 있는 A의 인접 노드인 C노드를 방문하고, 스택에 C노드를 추가합니다.

이후 스택의 top 부분에 있는 C의 인접 노드인 F를 방문하고, 스택에 F노드를 추가합니다.

이후 스택의 top 부분에 있는 F의 인접노드를 방문해야 하는데, F의 인접노드가 없으므로 스택에서 F노드를 제거합니다.

이후 스택의 top 부분에 있는 C의 인접 노드인 G노드를 방문하고, 스택에 G노드를 추가합니다.

이후 G, C, A의 인접 노드를 방문해야되는데 모두 방문하였으므로 모두 제거해줍니다.

스택이 비었으므로 DFS의 과정을 종료합니다.

 

DFS의 장단점 !

- 장점 

1. 현재 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적습니다.

2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있습니다.

3. BFS 보다 구현이 간단합니다.

- 단점 

1. 단순 검색 속도가 BFS 보다 느립니다.

2. 해가 없는 경우에 빠질 수 있습니다. 따라서 사전에 탐색할 임의의 깊이를 지정할 필요가 있습니다.

3. DFS는 해를 구하면 탐색이 종료됩니다. 따라서 구한 해가 최적의 해가 아닐 수 있습니다.

 

구현 코드가 필요하실 경우 제가 풀어 놓은 문제들을 참고하는 것을 권장합니다 !

그럼 20000~