1번부터 번호가 부여된 N개의 컴퓨터가 인터넷 선으로 서로 연결되어 있다. 이때, 한 컴퓨터가 바이러스에 감염이 되면, 1분이 경과된 후에는 그 컴퓨터와 인터넷 선으로 직접 연결된 컴퓨터들도 감염된다. 이때, 1번 컴퓨터가 최초로 바이러스에 감염되고 나서, N개의 컴퓨터들이 모두 바이러스에 감염되려면 몇 분이 소요되는지를 구하는 프로그램을 작성하시오.

예를 들어, 3개의 컴퓨터들이 인터넷 선으로 <그림 1>과 같이 서로 연결되어 있는 경우 1번 컴퓨터가 바이러스에 감염되고 2분이 지나면 모든 컴퓨터들이 감염되게 된다.

​

<그림1 >

​

3개의 컴퓨터들이 인터넷 선으로 <그림 2>와 같이 서로 연결되어 있는 경우 1번 컴퓨터가 바이러스에 감염되고 1분이 지나면 모든 컴퓨터들이 감염되게 된다.

​

<그림2 >

​

6개의 컴퓨터들이 인터넷 선으로 <그림 3>과 같이 서로 연결되어 있는 경우 1번 컴퓨터가 바이러스에 감염되고 2분이 지나면 모든 컴퓨터들이 감염되게 된다.

​

<그림3 >

​

실행파일의 이름은 EE.EXE로 한다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 컴퓨터의 수 N이 주어진다. N은 1 이상 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 인터넷 선으로 직접 연결되어 있는 컴퓨터의 쌍의 개수가 주어진다. 이어서 그 수 만큼 한 줄에 한 쌍씩 인터넷 선으로 직접 연결된 컴퓨터의 번호 쌍이 주어진다. (인터넷 선으로 직접 연결된 두 컴퓨터의 번호가 빈칸 1개를 사이에 두고 한 쌍으로 주어진다.)

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 1번 컴퓨터가 바이러스에 감염되었을 때, N개의 컴퓨터가 모두 바이러스에 감염되는 소요된 시간(분 단위)을 출력 파일의 첫째 줄에 출력한다.

입력과 출력의 예 1

입력 (INPUT.TXT)

3

2

1 2

2 3

​

출력 (OUTPUT.TXT)

2

​

입력과 출력의 예 2

입력 (INPUT.TXT)

3

2

1 2

1 3

​

출력 (OUTPUT.TXT)

1

​

입력과 출력의 예 3

입력 (INPUT.TXT)

6

5

1 2

1 4

2 3

4 5

4 6

​

출력 (OUTPUT.TXT)

2

​

//너비우선 탐색(BFS: Breadth First Search)

//queue1: First In First Out, 선입선출)

/*용도: 미로찾기, 프린터 출력처리,콜센터 고객 대기시간

윈도우 시스템 메시지 처리, 프로세스 관리 등에 이용 */

#include <stdio.h>

int main()

{

int n; // 컴퓨터 대수

int e; // 컴퓨터에 연결된 쌍의 수

int net[101][101]= {{0}}; //컴퓨터 최대수 100이하

int pshort[101]= {0}; // 인접행렬(연결된 컴) 가는 시간

int v[101]= {0}; // 방문여부 체크

int queue1[101]= {0}; //큐의 초기값

int head=0; // 행렬 처음을 표시

int tail=0; // 행렬의 끝을 표시

int i,j,k; //행렬

int max1=-99999; //가장 작은값으로 초기화

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; //연결된 컴퓨터 1로 표시

net[j][i]=1; //연결된 컴퓨터 1로 표시

}

queue1[tail++]=1; //tail이 가리키는 위치에 변수에 1분 초기값

v[1]=1; //1번째 컴 초기값 1

do

{

i=queue1[head++]; // queue1 head 변수 1증가(추출)

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

{

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

//인접행렬(연결된컴) 그리고 방문안했으면

{

queue1[tail++]=j; // tail방에 j 저장

v[j]=1; // 방문시 1로 표시

pshort[j]=pshort[i]+1; // 연결컴 가는 시간 1분씩 증가

max1=pshort[j];

//if(max1<pshort[j]) max1=pshort[j];

/*max1 초기값인 -99999 보다 연결된 컴퓨터 1분씩 증가한 값이 크면

방문시 1분씩 증가한 값을 max1에 대입 */

}

}

}

while(head!=tail);// 끝까지 탐색

printf("%d",max1);

return 0;

}