​

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2,3,5,6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

​

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. 실행파일의 이름은 CC.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력파일의 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력 형식

출력파일의 이름은 OUTPUT.TXT로 한다. 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)

7

6

1 2

2 3

1 5

5 2

5 6

4 7

​

출력 (OUTPUT.TXT)

2번컴 연결=>1

3번컴 연결=>1

5번컴 연결=>1

6번컴 연결=>1

바이러스 걸린 컴퓨터 대수:4대

​

// 깊이우선 탐색(Depth First Search: DFS, stack사용)

#include <stdio.h>

int net[101][101]; //컴퓨터 최대수

int v[101]={0}; //방문여부 초기값(방문 안한값)

int n; // 컴퓨터 수 7대

int cnt=0; // 바이러스에 걸린 1번 컴퓨터와 연결된 컴퓨터수 카운트

void DFS(int i){

int j;

v[i]=1; // 방문시1

for(j=1;j<=n;j++){

if(net[i][j]==1 && v[j]==0){

//인접행렬(연결된것만), 방문여부 v[j]=0

cnt++; //연결된 컴퓨터(바이러스 걸린 컴퓨터수)

// 검증

printf("\n %d번컴 연결=>%d",j, net[i][j]==1 && v[j]==0);

DFS(j); // 재귀적 호출, 방문하지 않은곳 방문

}

}

}

int main()

{

int i,j,k,e;

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

//입력

scanf("%d",&n); //컴퓨터 수 불러옴

scanf("%d",&e); //컴퓨터 연결된 쌍

for(k=0;k<e;k++){

scanf("%d %d",&i,&j); //연결된 컴퓨터

net[i][j]=1; //i, j 연결된것을 1로 표시

net[j][i]=1; //j, i 연결된것을 1로 표시

}

//처리

DFS(1); /* 1번 컴퓨터가 바이러스 걸렸을때, 만약에 DEF(4)로 하면 7번컴퓨터와 연결되어 출력값은 1임 */

//1번 컴퓨터와 연결된 컴퓨터(바이러스 걸린 컴퓨터수)

printf("\n\n 바이러스 걸린 컴퓨터 대수:%d대",cnt);

return 0;

}