[백준] 2606 바이러스

문제 : 컴퓨터 바이러스는 네트워크를 통해 전파된다. 만약 한 컴퓨터가 바이러스에 걸리면, 그 컴퓨터와 네트워크로 연결되어 있는 모든 컴퓨터는 바이러스에 감염되게 된다. 

위의 사진은 주어지는 네트워크와 컴퓨터의 구조를 예시로 든 것이며, 위의 경우에는 1번 컴퓨터가 감염되었을 때 2,3,5,6 컴퓨터가 감염이 가능한 것을 알 수 있다.

여기서, 1번 컴퓨터가 바이러스에 감염되었을 때, 1번 컴퓨터를 통해 감염될 수 있는 컴퓨터의 수를 구하시오.

입력 : 첫째 줄에는 컴퓨터의 수, 두번째 줄에는 컴퓨터 간의 네트워크 수, 마지막으로 그 수만큼 한 줄에 한 쌍씩 연결되어 있는 컴퓨터 쌍이 주어진다.

예시)

7

6

1 2

2 3

1 5

5 2

5 6

4 7

출력)

4

이 문제는 간단한 DFS 문제이다. 사실 BFS 로도 충분히 풀 수 있는데, 구현이 DFS가 조금 더 간단해서, DFS를 이용해서 풀어 보았다. 이것을 응용하면 바로 풀 수 있는 문제이다.

여기서, 그래프 탐색이란?

• 시작 정점부터 깊이를 기준으로 모든 노드를 한 번씩 방문하는 알고리즘
• 모든 노드를 방문하고자 할 때 쓰인다.
• 주로 재귀 호출을 이용하여 구현한다.

간단히 위의 사진을 이용해 DFS 구현 과정을 나타내자면 1-2-3-5-6 순으로 탐색할 것이다. 시작 노드는 1, 그 다음 순서의 노드는 2 이다. 다음 시작 노드는 2, 그 다음 순서의 노드는 3이다. 다음 시작 노드는 3, 그 다음 순서의 노드는 4가 나와야 하지만 연결되어 있지 않으므로, 다음 노드는 5 이다. 이러한 식으로 순차적으로 탐색하는 방법이다.

만약 해당 노드를 탐색했다면, 탐색한 노드는 방문했다는 표시를 해 두어야 다시 탐색하는 불상사가 없다. 이 문제는 시작 노드 1을 제외한 나머지 노드의 수 (컴퓨터의 수) 를 출력해야 하는 프로그램이므로, 탐색을 할 때마다 +1 을 해주면 간단하게 답이 나온다.

#include <stdio.h>
 
int com[101][101]={0};
int visit[101]={0}; 
int viruscom=0;
 
void dfs(int start,int net)
{
    int i;
    
    visit[start]=1;
    viruscom++;
 
    for(i=1;i<=net;i++)
    {
        if(com[start][i]==1 && visit[i]==0)
        {
            dfs(i,net);
        }
    }
    
    return;
}
 
int main()
{
    int num,net,x,y;
    scanf("%d",&num);
    scanf("%d",&net);
    for(int i=0;i<net;i++)
    {
        scanf("%d %d",&x,&y);
        com[x][y]=1;
        com[y][x]=1;
    }
    
    dfs(1,num);
    printf("%d",viruscom-1);
}