문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.
1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
이 문제는 그래프 탐색에 관한 문제이다. 문제의 그림도 그래프로 나와있고, 이 그래프에서 노드 1과 연결된 노드들의 개수를 찾는 것이 이번 문제의 목표이다.
그래프 탐색 알고리즘은 DFS, BFS 등등이 있다. 이번에는 DFS를 이용하여 문제를 풀어보았다.
DFS(깊이 우선 탐색, Depth First Search)는, 그래프의 깊이를 우선순위로 하여 그래프를 탐색하는 방법이다. 그래서, 자신과 만나는 노드에 도착하면, 그 노드와 만나는 노드를 또 다시 탐색해나가는 모습을 보여준다.
BFS(너비 우선 탐색, Breadth First Search)는, 그래프의 너비를 우선순위로 하여 그래프를 탐색하는 방법이다. DFS와는 다르게, 자신과 접하는 노드 전부를 한번에 큐에 저장하는 모습을 볼 수 있다.
우선, 연산의 수를 줄이기 위해 노드를 방문했을 때, 그 노드를 이전에 방문했는지에 대한 배열이 필요하다. 그리고, 이 그래프를 넣을 배열이 필요하므로 전역 변수로 설정해준다 (1번).
전체 컴퓨터 수와 입력받을 데이터 수를 입력받고 (2번), 데이터를 입력받으면서 연결되어 있는 노드를 모두 1로 바꾼다. 전역변수를 설정하면 0으로 초기화가 되고, array의 index를 입력받은 수 - 1을 해주는 이유는 배열은 0에서 시작하고, 컴퓨터 번호는 1부터 시작하기 때문이다 (3번).
이후 DFS를 1에서부터 실행해주면 된다 (4번).
#include <stdio.h>
#include <stdlib.h>
#define NUM 100
int visit[NUM]; // 1
int array[NUM][NUM];
int sol;
void dfs(int, int);
int main(void) {
int total_com;
scanf("%d", &total_com); // 2
int total_data;
scanf("%d", &total_data);
int a, b;
for (int i = 0; i < total_data; i++) { // 3
scanf("%d %d", &a, &b);
array[a - 1][b - 1] = 1;
array[b - 1][a - 1] = 1;
}
visit[0] = 1;
dfs(total_com, 0); // 4
printf("%d\n", sol);
return 0;
}
void dfs(int total, int num) {
for (int i = 0; i < total; i++) {
if (visit[i] == 0 && array[num][i] == 1) {
visit[i] = 1;
dfs(total, i);
sol++;
}
}
}dfs의 실행 순서는 이렇다.
- 시작할 노드에서 연결되어 있으면서 현재 방문하지 않은 노드를 찾는다.
- 그 노드에 방문하면서, 방문 표시를 한다.
- 방문한 노드를 시작 노드로 잡으면서, 그 노드에 연결되어 있으면서 방문하지 않은 노드를 찾는다.
현재 시작 노드는 1이다. 위의 문제 그림 1의 그래프에서 dfs를 한다고 가정하겠다.
1에서 시작해서, 연결되어 있으면서 방문하지 않은 노드를 찾는다. 그러한 노드는 2번 노드가 되고, 이 노드를 방문하면서 2번과 연결되어 있으면서 방문하지 않은 노드를 또 찾는 것이다.
이런 식으로 가면, 1번과 연결된 모든 노드를 찾을 수 있고, 문제에서 요구하는 답을 낼 수 있다.
