백준 17835번: 면접보는 승범이네 (Java)

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

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개가 공백을 두고 주어진다.

출력

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

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

 

---

 

 

K개의 면접장마다 K번의 다익스트라를 돌려야하는 풀이밖에 생각이 안났다. 시간 복잡도가 O(N^2logN)으로, 당연히 시간초과가 뜨는 풀이이다.

 

풀이

0. 면접장에서 집을 가는 거리의 최댓값을 구하면 된다.

1. 시작점을 한 번에 우선순위 큐에 넣어주면 된다.

2. 주어진 조건은 '집에서 면접장'으로 가는 거리이나, 문제를 용이하게 풀기 위해서 '면접장에서 집'으로 가는 거리를 구하기에, 입력값을 거꾸로 넣어줘야 한다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    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 M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }
        
        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 dist = Integer.parseInt(st.nextToken());
            graph.get(v).add(new Edge(u, dist));
        }
        
        long ans = 0;
        int ansLoc = 0;
        st = new StringTokenizer(br.readLine());
        long[] dist = new long[N+1];
        Arrays.fill(dist, 100_000_000_000L);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (int i = 0; i < K; i++) {
            int exam = Integer.parseInt(st.nextToken());
            pq.offer(new Edge(exam, 0));
            dist[exam] = 0;
        }
        
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int curLoc = cur.loc;
            long curDist = cur.dist;
            if (dist[curLoc] < curDist) continue;
            for (Edge nxt: graph.get(curLoc)) {
                int nxtLoc = nxt.loc;
                long nxtDist = curDist + nxt.dist;
                if (nxtDist < dist[nxtLoc]) {
                    dist[nxtLoc] = nxtDist;
                    pq.offer(new Edge(nxtLoc, nxtDist));
                }
            }
        }
        
        for (int i = 1; i <= N; i++) {
            if (ans < dist[i]) {
                ans = dist[i];
                ansLoc = i;
            }
        }
        System.out.println(ansLoc);
        System.out.println(ans);
    }
    
    static class Edge implements Comparable<Edge>{
        int loc;
        long dist;
        
        public Edge(int loc, long dist) {
            this.loc = loc;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}