2606)바이러스

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

주어진 예제를 그래프로 표현하면 아래 그림과 같다.

1번 컴퓨터에 어떻게든 연결된 컴퓨터는 감염된다.

우선 네트워크를 표현하기 위해 이차원 배열을 할당하고 두 노드 사이에 간선이 있으면 TRUE를 저장한다.

1번 노드에서 1~n번 노드 중 간선이 있는 경우 그 노드를 방문한다.

방문한 노드가 i번 노드일 때 해당 노드에 감염 여부를 TRUE로 바꿔준다.

i번 노드에서 1~n번 노드 중 간선이 있을 때 그 노드를 방문한다.

이미 감염된 경우 빠져나온다.

#include<stdio.h>
#define TRUE 1
#define FALSE 0
 
void visitNet(int **net, int *infection, int n, int start) {
    if (infection[start]) return;
    
    infection[start] = TRUE;
 
    for (int end = 0; end < n; end++) {
        if (net[start][end]) {
            visitNet(net, infection, n, end);
        }
        
    }
}
 
int main() {
    int n, conn;
    int **net;
    int *infection;
    int start, end;
    int count = 0;
 
    scanf("%d %d",&n,&conn);
 
    net = (int **)malloc(sizeof(int *)*n);
    for (int i = 0; i < n;i++) {
        net[i] = (int *)calloc(n,sizeof(int));
    }
    infection = (int **)calloc(n, sizeof(int));
 
    for (int i = 0; i < conn;i++) {
        scanf("%d %d",&start, &end);
        start--, end--;
        net[start][end] = TRUE;
        net[end][start] = TRUE;
    }
 
    visitNet(net,infection,n,0);
 
    for (int j = 0; j < n; j++) {
        count += infection[j];
    }
    printf("%d\n",count-1);
 
    return 0;
}