Baekjoon 6118 숨바꼭질 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가 공백을 사이에 두고 주어진다.

출력

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

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

풀이

직전에 풀었던 결혼식과 비슷한 문제이다.

2022.06.10 - [Algorithm/Baekjoon] - Baekjoon 5567 결혼식 JAVA

 

다만 앞에서의 몇 번째의 친구의 관계인지를 파악하는 값을 헛간의 거리라고 생각하고,

새로운 값으로 헛간의 거리가 갱신될 때마다, 같은 거리를 갖는 헛간의 개수를 초기화하고 카운팅을 하면서 값을 찾는다.

동시에 최소의 숫자를 가지는 헛간의 번호도 갱신한다.

자세한 것은 코드 참고

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m=Integer.parseInt(st.nextToken());
		int ac=0, ad=0, as=0; // 헛간의 번호, 헛간까지의 거리, 같은 거리를 갖는 헛간의 개수 
		boolean [] chk = new boolean[n+1];
		ArrayList<ArrayList<Integer>>list = new ArrayList<ArrayList<Integer>>();
		// LinkedList를 사용하면 시간초과 오류 발생
		for(int i=0;i<=n;i++)	// 리스트 초기화
			list.add(new ArrayList<>());
		
		for(int i=0;i<m;i++) {	// 헛간은 양방향으로 이루어져 있음
			st = new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken()), b=Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {1,0});	// 탐색은 첫번째부터 시작하기에 1번 헛간을 방문처리 
		chk[1]=true;
		while(q.size()>0) {
			int [] tmp=q.poll();
			int cur = tmp[0], depth=tmp[1];
			if(depth==ad) {	// 깊이가 동일하면 여러개의 헛간이기에 
				ac=Math.min(ac,cur);	// 헛간 번호가 작은 헛간을 저장
				as++;	// 헛간의 개수를 증가
			}
			else if(depth>ad) {	// depth가 증가 했다면 더 깊은 헛간이 있기에
				ac=cur;	// 헛간의 번호를 바꾸고
				ad=depth; // 헛간의 거리를 최신화
				as=1;	// 헛간의 개수를 1로 초기화
			}
			for(int i=list.get(cur).size()-1;i>=0;i--) {
				int adj = list.get(cur).get(i);	// 인접해 있는 헛간을 탐색
				if(!chk[adj]) {	// 이미 탐색한 헛간이라면 탐색하지 않음
					chk[adj]=true;
					q.add(new int[] {adj, depth+1});
				}
			}
		}
		System.out.println(ac+" "+ad+" "+as);
	}
}