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

: ) YOUNG·2024년 3월 29일
1

알고리즘

목록 보기
344/422
post-thumbnail

백준 17835번
https://www.acmicpc.net/problem/17835

문제



생각하기


  • 다익스트라 문제이다.

  • 다익스트라 문제중에 진짜 괜찮은 문제인 것 같음

  • 문제이해를 잘해야 코드가 왜 이렇게 되는지도 이해할 수 있다.



동작

⭐ 이문제의 핵심은 문제에서 어떤 도시에서든 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다. 이 문장이다.

왜 이 문장이 중요하냐 -> 바로 단방향 그래프이기 때문이다.

N개의 각 도시에서 K개의 면접장까지 최단 거리를 구하려면, N 번의 다익스트라를 해야되는데 이러면 시간이 오래걸린다.

대략 O(100,000×(500,000+100,000)log100,000)O(100,000×(500,000+100,000)log100,000) -> 1,020,000,000,0001,020,000,000,000 정도라고 하는데... 아무튼 그렇다

이렇게 하면 시간이 너무 오래걸려서 계산을 할 수 없기 때문에 어쨌든 N보다 작거나 같을 K에서 N까지의 거리를 구하면 한번의 다익스트라를 실행하면 문제를 해결할 수 있다.

각 면접장 노드를 PriorityQueue에 모두 넣으면 가장 가까운 노드를 갱신하면서 찾아가기 때문이다. 이렇게 하면 자연스럽게 각 노드별로 가장 가까운 면접장을 찾을 수 있다.

이게 단방향 그래프이기 때문과 어떤 도시에서는 하나의 면접장으로 이어지는 길이 있는 점을 거꾸로 돌려서 어떤 면접장이든 하나의 도시로는 갈 수 있다로 변경하는 것이다. 그래서 역방향으로 노드를 변경하는 것이다.

즉, 문제에서는 U -> V 이지만, V -> U로 구현하는 것이다.


        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());

            adjList.get(v).add(new Edge(u, c));
        }



이후에 각 면접장에서 출발 할 수 있도록 모두 pque에 넣는다.


        for (int i = 0; i < K; i++) {
            int temp = Integer.parseInt(st.nextToken());
            dist[temp] = 0;
            pque.offer(new Edge(temp, 0));
        }

각 면접장에서 출발하므로 dist[temp]는 똑같이 0으로 해주고~




이 다음은 똑같이 다익스트라 실행하면 면접장에서 출발해서 각 노드별 최단거리를 구할 수 있다.


        dijkstra();
        for (int i = 1; i <= N; i++) {

            if (maxDist < dist[i]) {
                maxDist = dist[i];
                ansNum = i;
            }
        }



결과


코드



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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, K;
    private static List<List<Edge>> adjList;
    private static final long INF = Long.MAX_VALUE;
    private static long[] dist;
    private static PriorityQueue<Edge> pque;

    private static class Edge implements Comparable<Edge> {
        int num;
        long dist;

        private Edge(int num, long dist) {
            this.num = num;
            this.dist = dist;
        }

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

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        long maxDist = 0;
        int ansNum = 0;


        dijkstra();
        for (int i = 1; i <= N; i++) {

            if (maxDist < dist[i]) {
                maxDist = dist[i];
                ansNum = i;
            }
        }

        sb.append(ansNum).append('\n').append(maxDist);

        return sb.toString();
    } // End of solve()

    private static long[] dijkstra() {
        boolean[] isVisited = new boolean[N + 1];

        while (!pque.isEmpty()) {
            Edge current = pque.poll();

            if (isVisited[current.num]) continue;
            if (dist[current.num] < current.dist) continue;
            isVisited[current.num] = true;

            for (Edge next : adjList.get(current.num)) {
                if (dist[next.num] > dist[current.num] + next.dist) {
                    dist[next.num] = dist[current.num] + next.dist;
                    pque.offer(new Edge(next.num, dist[next.num]));
                }
            }
        }

        return dist;
    } // End of dijkstra()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 도시의 수
        M = Integer.parseInt(st.nextToken()); // 도로의 수
        K = Integer.parseInt(st.nextToken()); // 면접장의 수

        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        dist = new long[N + 1];
        Arrays.fill(dist, INF);

        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());

            adjList.get(v).add(new Edge(u, c));
        }

        pque = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            int temp = Integer.parseInt(st.nextToken());
            dist[temp] = 0;
            pque.offer(new Edge(temp, 0));
        }
    } // End of input()
} // End of Main class

0개의 댓글