DFS(깊이 우선 탐색).c

DFS란 (Depth-First Search)라고 해요. 해석하자면 깊이를 우선해서 탐색한다?라고 할 수 있습니다. 무조건 한 우물만 판다는 얘기라고 생각할 수 있습니다.

천천히 한번 봐볼게요.

일단 이런 그래프가 있다고 가정하겠습니다. 모든 간선은 양방향입니다.

이 그래프를 DFS를 적용해서 탐색하는 순서는 작은 숫자를 먼저 탐색한다 하면 결과는 (1->2->3->4->5->4->6->4->3->2->1)입니다.

그림으로 순서를 보겠습니다.

먼저 1에 방문합니다. 그다음 1은 방문했다고 체크해둡니다. 1에서 갈 수 있는 곳은 2와 5입니다. 작은 수 먼저 탐색하기로 하였으니 다음은 2로 이동합니다.

2에 방문합니다. 2는 방문했다고 체크해두고, 2에서 갈 수 있는 곳은 1, 3, 4, 5인데요, 1은 아까 방문했으니 3, 4, 5중에 작은 3에 방문합니다.

3에 방문합니다. 3에 방문했다고 체크해두고, 3에서는 2, 4에 갈 수 있네요. 하지만 2에 이미 방문했으니 4로 갑니다!

4에 방문합니다. 4를 방문했다고 체크하고, 4에서는 2, 3, 5, 6을 갈 수 있네요. 2, 3은 이미 방문했으니 5, 6중에 작은 수인 5로 갑니다.

5에 방문합니다. 5에서는 1, 2, 4에 갈 수 있네요. 하지만 1, 2, 4모두 이미 방문했던 곳이므로 5 이전에 있었던 곳(4)으로 갑니다. 여기서 5에서 탐색은 끝난거죠.

다시 4로 와서, 아까 4에서는 2, 3, 5, 6을 갈 수 있었죠? 2, 3은 방문 했었기 때문에 못갔고 5는 탐색이 끝났으니 남은 6에 가야겠네요!

6에 방문하고, 방문했다고 체크해둡니다. 6에서는 4에 갈 수 있지만 이미 방문했으니 6에서도 탐색은 끝난겁니다! 따라서 전에 있던 곳(4)로 갑니다.

4로 돌아와서, 4에서는 2, 3, 5, 6에 갈 수 있었는데 2, 3은 이미 방문했고, 5, 6은 탐색이 끝났군요. 따라서 이전에 있던 곳(3)으로 갑니다. 여기서도 4에서의 탐색은 끝!!!

3으로 돌아와서, 아까 3에서는 2, 4에 갈 수 있었는데 2는 이미 방문했고, 4는 탐색이 끝났네요. 그렇다면 이전에 있던 곳(2)으로 갑니다. 3에서의 탐색은 끝.

2로 돌아와서, 아까 2에서는 1, 3, 4, 5에 갈 수 있었는데 1은 이미 방문했고, 3, 4, 5는 탐색이 끝났으니 여기서도 원래 있던 곳(1)으로 가야겠네요. 2에서의 탐색은 끝!

1로 돌아왔습니다. 1에서는 2, 5에 갈 수 있었는데, 두곳 모두 탐색이 끝났네요! 그리고 이전에 있던곳도 없으므로 탐색 종료!!

깊이 우선 탐색 끝!!

그림을 보면 탐색 도중에 탐색이 끝났으면 이전 곳으로 돌아가는 Backtracking이 발생합니다. 이것이 발생하면, 그곳에서는 탐색이 끝났다고 볼 수 있습니다.

이것을 C로 표현해보면

#include <stdio.h>
#include <stdbool.h>
#define MAX 1001
 
int Graph[MAX][MAX];
bool visited[MAX];
int N, M;
 
void dfs(int k) {
    visited[k] = true;
    for (int i = 1; i <= N; i++) {
        if (visited[i] != false || Graph[k][i] == 0) continue;
        dfs(i);
    }
}
 
int main(void) {
 
    scanf("%d%d", &N,&M);
 
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        Graph[u][v] = 1;
        Graph[v][u] = 1;
    }
    
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
 
 
    return 0;
}