백준 17835 (면접보는 승범이네) - java

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

 

문제

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

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

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

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

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

 

유형 : 다익스트라

 

접근 방식

• 면접장이 아닌 지점을 기준으로 다익스트라를 전부 수행한다면 시간 초과를 맛보게 될 것이다.
• 중요한 점은 다익스트라를 한번만 수행하여 결과를 얻는 것이다.
  • PQ에 모든 면접장의 정보를 넣고 다익스트라를 수행한다.
  • 여기서 중요한 점은 간선이 "단방향"이라는 것이다. 면접장으로부터 역으로 탐색하는 것이기 때문에 모든 간선의 정보를 반대로 저장한다.
  • 그리고 탐색 중 다른 면접장을 만난다면 탐색을 건너뛴다.

 

전체 코드

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

public class Main {
    static int n,m,k;
    static ArrayList<int[]> graph[];

    static boolean[] isIt;
    static long[] dis;

    static PriorityQueue<Point> pq = new PriorityQueue<>(
            (x,y) -> Long.compare(x.c,y.c)
    );

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        dis = new long[n+1];
        isIt = new boolean[n+1];

        graph = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++) {
            graph[i] = new ArrayList<>();
            dis[i] = Long.MAX_VALUE;
        }

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[v2].add(new int[]{v1,c});
        }

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= k ; i++) {
            int node = Integer.parseInt(st.nextToken());
            pq.add(new Point(node,0l));
            dis[node] = 0l;
            isIt[node] = true;
        }

        go();
        br.close();
    }

    static void go() {
        while(!pq.isEmpty()) {
            Point cur = pq.poll();

            if(dis[cur.v] < cur.c)
                continue;

            for(int[] next : graph[cur.v]) {
                if(isIt[next[0]])
                    continue;

                if(dis[next[0]] > cur.c + next[1]) {
                    dis[next[0]] = cur.c + next[1];
                    pq.add(new Point(next[0],dis[next[0]]));
                }
            }
        }

        int maxIdx = 0;
        long maxNum = 0;

        for(int i = 1 ; i <= n ; i++) {
            if(maxNum < dis[i]) {
                maxIdx = i;
                maxNum = dis[i];
            }
        }

        System.out.println(maxIdx);
        System.out.println(maxNum);
    }

    static class Point {
        int v;
        long c;

        Point(int v,long c) {
            this.v = v;
            this.c = c;
        }
    }
}