[백준] 17835. 면접 보는 승범이네

문제 링크

1. 문제 설명

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 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개가 공백을 두고 주어진다.

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

2. 문제 접근

일반적인 다익스트라는 한 노드에서만 다른 노드까지 거리를 구하는 데 이 문제의 경우 여러 노드에서 다른 노드까지 거리를 구하는 것을 요구합니다.

여기서 일차원적으로 생각한다면 다익스트라를 여러 번 돌리면서 한 노드에서 다른 모든 노드까지 거리를 구하는 방법을 K번 반복하는 방식의 풀이를 할 수 있습니다. 사실 저도 처음에 그랬.. 아무튼 노드 수의 범위도 많고 K가 최대 N까지 커지는 최악의 경우 문제의 시간 복잡도가 일반 다익스트라 * K가 되므로 시간 제한 내에 풀이가 불가능합니다.

그래서 여러 노드에서 나머지 노드에 대한 최단 거리를 구하는 방법은 생각보다 간단합니다. 시작점을 여러 개를 둬서 시작 노드들의 거리를 0으로 놓고 동시에 출발하면 됩니다. 그러면 각 노드에서 가장 가까운 출발 노드에 대한 거리를 한 번의 다익스트라 알고리즘으로 구할 수 있습니다.

그럼에도 정답률이 유독 낮은 게 문제의 조건이 약간 까다롭습니다. 우선 면접장이 출발 노드가 아니고 도착 노드이기 때문에 그래프에 역방향으로 입력해야 합니다. 간선이 단방향이며 최악의 경우 거리의 총합이 자바의 int 범위를 벗어나므로 long 처리까지 해줘야 합니다.

3. 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Edge implements Comparable<Edge>{

        private int to;
        private long dist;

        public Edge(int to, long dist) {
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return Long.compare(dist, o.dist);
        }
    }

    static int n,m;
    static ArrayList<Edge>[] map;
    static Queue<Integer> queue = new LinkedList<Integer>();
    static Long[] totalDist;

    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());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        map = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) map[i] = new ArrayList<Edge>();
        totalDist = new Long[n+1];
        Arrays.fill(totalDist, Long.MAX_VALUE);

        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());
            map[v].add(new Edge(u,c));
        }

        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            queue.offer(Integer.parseInt(st.nextToken()));
        }

        dijikstra();

        Long maxDist = 0L;
        int maxNode = 0;

        for (int i = n; i >= 1; i--) {
            if (maxDist <= totalDist[i]) {
                maxNode = i;
                maxDist = totalDist[i];
            }
        }

        System.out.println(maxNode);
        System.out.println(maxDist);

    }

    private static void dijikstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Long[] dist = new Long[n+1];
        Arrays.fill(dist, -1L);

        for (int start : queue) {
            dist[start] = 0L;
            pq.offer(new Edge(start, 0));
        }

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (dist[cur.to] == -1 || dist[cur.to] < cur.dist) continue;
            for (Edge next: map[cur.to]) {
                if (dist[next.to] == -1 || dist[next.to] > dist[cur.to] + next.dist) {
                    dist[next.to] = dist[cur.to] + next.dist;
                    pq.offer(new Edge(next.to, dist[next.to]));

                }

            }
        }

        for (int i = 1; i <= n; i++) {
            totalDist[i] = Math.min(totalDist[i], dist[i]);
        }

    }
}