[이것이 코딩 테스트다] 숨바꼭질

문제

문제의 저작권은 ‘이것이 코딩테스트다’ 교재에 있습니다.

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결한다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어진다.

동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단한다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미한다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하라

입력 조건

• 첫째 줄에는 N, M이 주어지며, 공백으로 구분한다.
  • 2 <= N <= 20,000
  • 1 <= M <= 50,000
• 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어진다.
  • 1 <= A, B <= N

출력 조건

1) 숨어야 하는 헛간 번호

• 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력

2) 그 헛간까지의 거리
3) 그 헛간과 같은 거리를 갖는 헛간의 개수

입력 예시

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

출력 예시

4 2 3

접근방식

출발노드에서 도착노드까지의 최단거리를 먼저 구해야 하므로 다익스트라 알고리즘을 사용하였다.

1) pq를 사용해서 가장 최단거리가 짧은 노드 먼저 꺼내주고, 다음 노드와 비교해서 거쳐가는 경우가 더 짧으면 갱신 후 pq에 넣어주는 식으로 최단거리를 구해준다.

2) 다 구했으면 문제의 답은 최단거리가 가장 먼 헛간의 번호를 출력해주는것이므로 최단거리가 가장 먼 노드의 번호와 그때의 거리를 구하고, 이 거리와 같은 노드들의 개수를 출력한다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M; // 헛간 수(정점), 통로 수(간선)
	static final int INF = 1000000000;
	static ArrayList<Node>[] adjList; // 간선정보 저장
	static int[] dist; // 최단거리 저장
	static PriorityQueue<Node> pq;

	static class Node implements Comparable<Node> {
		int num, dist; // 정점 번호, 비용

		public Node(int num, int dist) {
			this.num = num;
			this.dist = dist;
		}

		@Override
		public int compareTo(Node o) { // 가중치 최소값 pop
			return this.dist - o.dist;
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		adjList = new ArrayList[N + 1];

		for (int i = 1; i <= N; i++)
			adjList[i] = new ArrayList<>();

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			adjList[x].add(new Node(y, 1));
			adjList[y].add(new Node(x, 1));
		}

		dijkstra(); // 그래프 탐색
		showAns(); // 답 구하기
	}

	private static void showAns() {
		int maxNode = 0; // 최단 거리가 가장 먼 노드번호(여러개면 더 작은 번호)
		int maxDist = -1; // 최단거리가 가장 먼 노드와의 최단거리
		int maxCnt = 0; // maxNode와 거리가 같은 노드들의 개수

		for (int i = 1; i <= N; i++) {
			//if (dist[i] > maxDist) {
        if (dist[i]!=INF &&dist[i] > maxDist) {
				maxDist = dist[i];
				maxNode = i;
			}
		}

		for (int i = 1; i <= N; i++) {
			if (maxDist == dist[i]) maxCnt++;
		}

		System.out.println(maxNode + " " + maxDist + " " + maxCnt);
	}

	private static void dijkstra() {
		pq = new PriorityQueue<Node>(); // 최소 가중치 먼저 나옴

		// 초기 세팅
		pq.add(new Node(1, 0)); // 1번 노드부터 시작
		dist = new int[N + 1];
		Arrays.fill(dist, INF); // 최대값으로 세팅
		dist[1] = 0;

		while (!pq.isEmpty()) {
			Node now = pq.poll(); // 가장 최단거리 노드 pop

			if (now.dist > dist[now.num])
				continue; // 이미 방문했던 노드면 pass
			for (Node next : adjList[now.num]) { // 인접한 노드들 탐색
				if (dist[next.num] > dist[now.num] + next.dist) { // 현재 노드에서 다른 노드를 거치는 거리가 더 짦으면 갱신
					dist[next.num] = dist[now.num] + next.dist;
					pq.add(new Node(next.num, dist[next.num]));
				}
			}
		}
	}
}