[C언어] 백준 2606번 - 바이러스

https://www.acmicpc.net/problem/2606

문제

발상

DFS (깊이 우선 탐색, Depth-First Search)

이 문제는 DFS를 이용하여 풀어야 하는 전형적인 문제이다.
DFS란, 임의의 시작 노드에서 출발하여 다음 갈림길(Branch)로 넘어가기 전에 해당하는 길을 끝까지 파고 들어 탐색하는 방식을 의미한다.
더 이상 방문할 자식 노드가 없으면, 최근에 지나갔던 갈림길로 다시 되돌아가 다른 경로를 탐색하는 과정을 반복한다.
일반적으로 스택(Stack)이나 재귀 함수를 통해 구현한다.

임의의 시작 노드를 0이라고 할 때, 0번 노드에는 갈림길이 있고, 자식 노드로는 1번 노드와 2번 노드가 존재한다.
먼저 1번 노드부터 방문한다. 1번 노드에도 갈림길이 있고, 자식 노드로는 3번 노드와 4번 노드가 있다.
먼저 3번 노드를 방문한다. 3번 노드에는 갈림길이 없으므로 끝에 도달했다.
끝에 도달했으므로, 우리는 다시 이전에 지나갔던 갈림길로 되돌아간다. (1번 노드의 갈림길)
이전에 방문하지 않은 4번 노드를 방문한다. 4번 노드에도 갈림길이 없으므로 끝에 도달했다.
다시 이전에 지나갔던 갈림길로 되돌아왔지만, 여기에는 다 지나간 길밖에 없다.

그러므로 그 이전에 지나갔던 갈림길로 되돌아간다. (0번 노드의 갈림길)
이제 2번 노드를 방문한다. 2번 노드에는 갈림길이 있고, 자식 노드로는 5번 노드와 6번 노드가 존재한다.
먼저 5번 노드를 방문한다. 5번 노드에는 갈림길이 없으므로 끝에 도달했다.
다시 이전에 지나갔던 갈림길로 되돌아가(2번 노드의 갈림길), 6번 노드를 방문한다.
6번 노드에는 갈림길이 없으므로 끝에 도달했다.
다시 이전에 지나갔던 갈림길로 되돌아왔지만, 여기에는 다 지나간 길밖에 없다.

그러므로 그 이전에 지나갔던 갈림길로 되돌아간다. (0번 노드의 갈림길)
하지만 시작 노드의 갈림길도 전부 지나간 길만 존재한다. 이러면 탐색이 끝이다.

아래는 위 이미지를 바탕으로 만든 예시 코드와 출력값이다.

#include <stdio.h>

#define N 7; // 노드의 개수
int graph[N][N]; // 노드 간의 연결 관계 (인접 행렬)
int visited[N]; // 방문했는지

void dfs(int v) {
    visited[v] = 1;
    printf("%d ", v);

    for (int i=0; i<n; i++) {
        if (graph[v][i] == 1 && !visited[i]) { // v와 i가 연결되어 있고, i를 아직 방문하지 않았다면
            dfs(i);
        }
    }
}

int main() {
    // 0-1, 0-2, 1-3, 1-4, 2-5, 2-6

    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;
    graph[2][5] = graph[5][2] = 1;
    graph[2][6] = graph[6][2] = 1;

    dfs(0); // 시작점 = 0
    return 0;
}

0 1 3 4 2 5 6

Clang

#include <stdio.h>
#include <stdlib.h>

int count = 0;

void dfs(int v, int n, int** graph, int* visited) {
    visited[v] = 1;
    for (int i=1; i<=n; i++) {
        if (graph[i][v] == 1 && !visited[i]) {
            count++;
            dfs(i, n, graph, visited);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int** graph = (int**)malloc(sizeof(int*)*(n+1));
    for (int i=0; i<=n; i++) {
        graph[i] = (int*)malloc(sizeof(int)*(n+1));
    }
    int* visited = (int*)malloc(sizeof(int)*(n+1));

    int e;
    scanf("%d", &e);

    for (int i=0; i<e; i++) {
        int a,b;
        scanf("%d %d", &a, &b);
        graph[a][b] = graph[b][a] = 1;
    }

    dfs(1, n, graph, visited);

    printf("%d", count);

    for (int i=0; i<=n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(visited);

    return 0;
}