최단 경로 - 4. 숨바꼭질

문제

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

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

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

출력 조건
숨어야 하는 헛간 번호
거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력
그 헛간까지의 거리
그 헛간과 같은 거리를 갖는 헛간의 개수

입력 예시

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

출력 예시
4 2 3

구현코드

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

class Node implements Comparable<Node>{
	private int index;
	private int distance;
	public Node(int index, int distance){
		this.index = index;
		this.distance = distance;
	}
	public int getIndex(){
		return this.index;
	}
	public int getDistance(){
		return this.distance;
	}
	
	@Override
	public int compareTo(Node other){
		return Integer.compare(this.distance, other.distance);
	}
	
}
public class Main{
	public static int[] d;
	public static int INF = (int)1e9;
	public static ArrayList<ArrayList<Node>>graph;
	public static void Dijkstra(){
		PriorityQueue<Node>pq = new PriorityQueue<>();
		d[1] = 0;
		pq.offer(new Node(1, 0));
		while(!pq.isEmpty()){
			Node now = pq.poll();
			int index = now.getIndex();
			int distance = now.getDistance();
			if(d[index] < distance) continue;
			for(int i = 0 ; i < graph.get(index).size(); i++){
				int cost = distance + graph.get(index).get(i).getDistance();
				if(cost < d[graph.get(index).get(i).getIndex()]){
					d[graph.get(index).get(i).getIndex()] = cost;
					pq.offer(new Node(graph.get(index).get(i).getIndex(), cost));
				}
			}
		}
	}
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		// 노드와 간선의 개수 입력받기
		int n = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		// 거리 선언후 최대값으로 초기화
		d = new int[n+1];
		Arrays.fill(d ,INF);
		// 그래프 선언 후 노드의 개수 +1 만큼 선언
		graph = new ArrayList<ArrayList<Node>>();
		for(int i = 0 ; i <= n ; i++){
			graph.add(new ArrayList<Node>());
		}
		// 그래프에 간선 할당
		for(int i = 0 ; i < e ; i++){
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int distance = 1;
			graph.get(start).add(new Node(end, distance));
			graph.get(end).add(new Node(start, distance));
		}
		Dijkstra();
		// 가장 최단 거리가 먼 노드 번호(동빈이가 숨을 헛간의 번호)
        int maxNode = 0;
        // 도달할 수 있는 노드 중에서, 가장 최단 거리가 먼 노드와의 최단 거리
        int maxDistance = 0;
        // 가장 최단 거리가 먼 노드와의 최단 거리와 동일한 최단 거리를 가지는 노드들의 리스트
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            if (maxDistance < d[i]) {
                maxNode = i;
                maxDistance = d[i];
                result.clear();
                result.add(maxNode);
            }
            else if (maxDistance == d[i]) {
                result.add(i);
            }
        }
        
        System.out.println(maxNode + " " + maxDistance + " " + result.size());
	}
}
}

코드해석

이 문제는 다익스트라 알고리즘을 사용하는 것은 똑같지만

		for(int i = 0 ; i < e ; i++){
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int distance = 1;
			graph.get(start).add(new Node(end, distance));
			graph.get(end).add(new Node(start, distance));
		}

양방향이기 때문에 두개를 넣어주면 된다. 다른건 똑같다고 보면 된다.