[백준] 17835번 : 면접보는 승범이네 - 자바(Java)

Problem 🔒

문제

https://www.acmicpc.net/problem/17835

 

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.

면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.

모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.

속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.

승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.

입력

첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다.

다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다.

마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.

출력

첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.

둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.

예제 입력 1

6 10 2
2 6 2
1 4 1
6 1 5
2 5 1
5 1 4
4 5 6
6 2 3
3 5 1
3 1 1
5 2 2
1 2

예제 출력 1

4
8

예제 입력 2

10 20 5
4 1 18
6 1 7
2 4 1
5 6 18
7 6 10
10 6 9
3 2 4
8 3 10
9 8 15
7 1 12
10 7 1
8 1 3
6 5 19
2 9 10
7 2 4
10 3 20
7 10 14
5 7 12
8 4 10
2 5 8
1 8 4 6 7

예제 출력 2

9
15

---

Approach ❌

역방향 그래프로 풀어도 면접장의 수(K)만큼 다익스트라를 돌려야한다고 생각했다.

K1에서 다른 모든 도시로 가는 최단 경로, K2에서 다른 모든 도시로 가는 최단 경로 …를 구해서 가장 가까운 면접장까지의 최단 거리를 찾는 풀이를 생각했다. 그래서 역방향 그래프로 풀어도 시간초과가 분명했다.

하지만, 모든 출발점(모든 면접장)을 한 큐에 비용을 0으로 추가하여 다익스트라를 돌리면, 우선순위 큐에서 가장 비용이 작은 노드를 탐색하기 때문에 다익스트라 1번으로도 면접장까지의 최단 거리를 찾을 수 있었다.

---

Approach ⭕

1. 역방향 그래프로 면접장까지의 최단 거리 찾기
   • 각 도시마다 면접장까지 최단거리를 찾기 위해서는 (N-K)번의 다익스트라 를 실행해야하기 때문에, 시간초과가 난다.
   • 다익스트라를 1번 실행할 때, 시간복잡도는 $O(2ElogE)$(E:간선의 수)로 총 1800만번의 연산이 일어난다. 
   • 그렇기에, 역방향 그래프를 이용하여 간선 방향을 반대로 뒤집고, 면접장에서 각 도시로 가는 최단거리를 구하면 각 도시에서 면접장으로 가는 최단거리가 된다.
   • 간선 방향을 뒤집었지만, 도시에서 면접장으로 가려면 같은 간선을 선택해야한다.
2. int 범위를 벗어나는 도로의 길이(C)
   • 많은 사람들이 이 조건을 놓쳐 틀리는 경우가 많은 것 같다.(나 역시도 그렇다 ㅠ)
   • 최단거리를 저장하는 배열을 Long 타입으로 선언하고, 값을 Long.MAX_VALUE로 초기화 해야한다.
   • 우선순위 큐에서 자료형은 Long 타입 배열로 선언하고, 우선순위 조건을 Long 타입 비용을 비교하는 방식으로 생성해야한다.
   • 큐에 넣는 값들도 long[] 타입으로 생성하여 추가하도록 한다.

알게된 점 😯

우선순위 큐(PriorityQueue)를 활용해 하나의 다익스트라 알고리즘으로 여러 출발점에서 동시에 최단 경로를 구할 수 있다는 점을 알게되었다.

---

Solution 💡

public class 면접보는승범이네 {
    static int N, M, K;
    static Long cost[];
    // 우선순위 큐에 Long을 비교하는 방식으로 수정
    static PriorityQueue<long[]> q = new PriorityQueue<>((a,b)->Long.compare(a[1], b[1]));
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken())+1;
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cost = new Long[N];
        Arrays.fill(cost, Long.MAX_VALUE); // Long.MAX_VALUE로 초기화
        for(int i=0; i<N; i++){list.add(new ArrayList<>());}
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(v).add(new int[]{u,c}); // 역방향 그래프 생성
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<K; i++){
            int k = Integer.parseInt(st.nextToken());
            q.add(new long[]{k,0L}); // 다익스트라 시작점으로 큐에 추가
            cost[k] = 0L;
        }
        while(!q.isEmpty()){
            long[] current = q.poll();
            int curNode = (int) current[0]; // cost 배열에 인덱스로 들어가야해서 int형
            long curCost = current[1];
            if(curCost>cost[curNode]) continue;
            for(int[] e : list.get(curNode)){
                int nextNode = e[0];
                long nextCost = curCost + e[1];
                if(nextCost<cost[nextNode]){
                    cost[nextNode] = nextCost;
                    q.add(new long[]{nextNode, nextCost});
                }
            }
        }
        int town = 0; // 거리가 가장 먼 도시
        long max = 0; // 거리
        for(int i=1; i<N; i++){
            if(cost[i]>max){max=cost[i]; town=i;}
        }
        System.out.println(town);
        System.out.println(max);
    }
}