[Java] 백준 6118번 : 숨바꼭질

문제

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.  

재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸다. 또한 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능하다고 생각해도 좋다. 

재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다. 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!

입력

첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어진다.

이후 M줄에 걸쳐서 A_i와 B_i가 공백을 사이에 두고 주어진다.

 

출력

출력은 한줄로 이루어지며, 세 개의 값을 공백으로 구분지어 출력해야한다. 

첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력한다), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야한다.

예제 입력 1

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

예제 출력 1

4 2 3

힌트

농장의 조감도는 아래와 같다. 

                   1--2--5
                   | /|
                   |/ |
                   3--4
                   |
                   6

헛간 4, 5, 6은 모두 2의 거리를 가진다. 여기서 4번 헛간을 선택하는 이유는 헛간의 번호가 가장 작기 때문이다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, M;
	private static int []depth;
	private static List<Integer> []list;
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		list=new ArrayList[N+1];
		for(int i=1;i<=N;i++) list[i]=new ArrayList<>();
		
		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		depth=new int[N+1];
		bfs();
		int max=0;
		for(int i=1;i<=N;i++) {	// 최대 거리를 구함
			if(depth[i]>max) {
				max=depth[i];
			}
		}
		int num=-1;
		int dist=max;	// 거리의 최댓값
		int cnt=0;
		for(int i=1;i<=N;i++) {
			if(depth[i]==max) {
				if(num==-1) num=i;	// 최초로 최대 거리가 나오는 경우
				cnt++;	// 최대 거리인 경우의 개수
			}
		}
		System.out.println(num+" "+dist+" "+cnt);
	}

	private static void bfs() {	// 헛간에서부터 떨어진 거리를 구해주기 위해 bfs를 돌면서 depth를 구해줌
		Queue<Integer> queue=new LinkedList<>();
		queue.add(1);
		
		boolean []visited=new boolean[N+1];
		visited[1]=true;
		depth[1]=0;
		
		int dep=1;
		while(!queue.isEmpty()) {
			int size=queue.size();
			
			while(size-->0) {
				int q=queue.poll();
				
				for(int i:list[q]) {
					if(!visited[i]) {
						visited[i]=true;
						depth[i]=dep;
						queue.add(i);
					}
				}
			}
			dep++;
		}
	}
}

시작점으로부터 가장 먼 거리를 찾아야 하며, 거리가 같은 경우의 개수를 모두 찾는 것은 같은 너비인 경우를 찾아주는 것과 같습니다. 그러므로 bfs를 통해 탐색해주었습니다.