[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

DFS란?

• DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다. DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다. 
• DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다.

 

DFS 예시

위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다.

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

이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다. (C노드를 먼저 방문해도 된다. 순서는 상관 없다)

 

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

이후 스택의 top 부분에 있는 D의 인접노드를 방문해야 하는데, 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노드를 추가한다.

 

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

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

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

 

스택이 비었으므로 DFS 과정은 종료된다.

 

---

DFS 장단점

DFS 장점

• 현재 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적음
• 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
• BFS 보다 구현이 간단함

DFS 단점

• 단순 검색 속도가 BFS 보다 느림
• 해가 없는 경우에 빠질 수 있음. 따라서 사전에 탐색할 임의의 깊이를 지정할 필요가 있다.
• DFS는 해를 구하면 탐색이 종료된다. 따라서 구한 해가 최적의 해가 아닐 수 있다.

---

DFS 구현

DFS 구현은 Stack 자료구조를 이용하거나 재귀를 통해 구현할 수 있다. 여기서는 재귀를 통해 구현하는 방식을 택하겠다. (C++ 이면 STL로 stack 을 이용하기 편하나 C언어는 그렇지 않기 때문에)

 

또한 인접행렬로 나타낸 그래프 혹은 인접리스트로 나타낸 그래프에서 각각 구현이 조금씩 다르다. 그래프에 대해서 조금더 알고 싶다면 다음 포스팅을 참고하자.

 

[자료구조] 그래프(Graph)의 개념과 이해, 용어 | 인접행렬 vs 인접리스트 그래프 구현

 

소스코드

#include <stdio.h>
 
int graph[11][11];    // 인접행렬로 구현한 그래프 
int visited[11];        // 방문 여부 체크 
 
int DFS(int cur, int n){
    int i;
    visited[cur] = 1;    // 현재 노드 방문 체크 
    for(i=1; i<=n; i++){    // 모든 인접한 노드 체크 
        if(graph[cur][i] == 1 && visited[i] == 0){    // 인접하고 방문하지 않은 노드라면 
            printf("%d ", i);
            DFS(i, n);
        }
    }
}
 
int main()
{
    int start = 1;
    graph[1][3] = 1; graph[3][5] = 1; graph[5][7] = 1; 
    graph[3][1] = 1; graph[5][3] = 1; graph[7][5] = 1; 
     
    graph[1][2] = 1; graph[2][4] = 1; graph[4][8] = 1;
    graph[2][1] = 1; graph[4][2] = 1; graph[8][4] = 1;
    
    printf("%d ",start);
    DFS(start,10); 
    
    return 0;
}

 

DFS는 위와 같이 재귀를 통해 구현할 수 있다. 이 때 중요한 점은 방문여부를 체크할 visited[] 배열이 필요하다는 것이다.

 

실행결과

 

 

 

 

 

---