백준 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번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //N, M 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //리스트로 그래프 생성
        List<Integer>[] graph=new List[n];
        IntStream.range(0, n).forEach(o -> graph[o] = new ArrayList<>());

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int src=Integer.parseInt(st.nextToken())-1;
            int dst=Integer.parseInt(st.nextToken())-1;

            graph[src].add(dst);
            graph[dst].add(src);
        }

        //{방문 노드, 비용} 중 비용을 기준으로 하는 최소힙
        PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(o->o[1]));
        pq.add(new int[]{0, 0});

        //1번 노드에서 모든 노드로의 거리 정보 배열
        int[] distance=new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0]=0;

        //방문 정보 배열
        boolean[] visited=new boolean[n];
        while(!pq.isEmpty()){
            int[] ptr = pq.poll();

            if(visited[ptr[0]])
                continue;
            visited[ptr[0]]=true;

            //연결된 모든 노드에 대해서 거리 정보를 갱신할 수 있으면 큐에 삽입
            for(int node:graph[ptr[0]]){
                if(visited[node] || distance[node]<ptr[1]+1)
                    continue;

                distance[node]=ptr[1]+1;
                pq.add(new int[]{node, ptr[1]+1});
            }
        }

        //결과 출력
        int max=Arrays.stream(distance).max().getAsInt();
        int count=(int)Arrays.stream(distance).filter(o->o==max).count();
        for(int i=0; i<n; i++) {
            if (distance[i] == max) {
                System.out.println(i + 1 + " " + distance[i] + " " + count);
                return;
            }
        }
    }
}

---

해결 과정

1. 1번에서 모든 노드로의 최소 거리를 구하면 된다. 다만 노드가 2만 개이기 때문에 2차원 배열로 그래프를 만들면 메모리 초과가 발생한다.

2. 😁