1238 - 파티 (Java)

 

---

 

문제

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

 

풀이

다익스트라 문제이다.

 

단순히 n개 각각 마을에서 x 마을로의 최단 거리를 다익스트라로 구하고,

그리고 x 마을에서 n개의 마을로의 최단거리를 다익스트라로 구해도 풀리긴한다.

 

x마을에서 n개 마을로의 거리는 한번만에 다 구할 수 있으나,

n개의 마을에서 x 최단거리를 구하기 위해서는 n + 1 번의 다익스트라를 돌아야하기에 굉장히 비효율적이다.

 

해결법은 간선의 방향을 반대로 하고 다익스트라를 수행하면 n 개의 마을에서 x 로 가는 가중치를 한번에 구할 수 있다.

n개 각각 마을에서 x로 향하는 길들을 반대로 설정하고 x에서의 다익스트라를 수행하면,

그건 각 마을에서 x로 향하는 최단거리가 된다.

 

이렇게 하면 단 두번의 다익스트라로 문제를 풀이할 수 있다.

 

(처음에는 나도 N + 1 번으로 풀었는데, 아닌거 같아서 찾아보니 이렇게 하는거였다..)

 

코드

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

public class Main {

    static class Node {
        int num;
        int weight;

        public Node(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }
    }

    public void solution() throws Exception {

        // Input
        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 x = Integer.parseInt(st.nextToken());

        int[][] graph = new int[n+1][n+1];
        int[][] reverseGraph = new int[n+1][n+1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            graph[from][to] = weight;
            reverseGraph[to][from] = weight;
        }


        // Dijkstra
        int[] resReverse = dijkstra(x, n, reverseGraph); // 각 정점에서 x 까지의 값
        int[] res = dijkstra(x, n, graph);  // x에서 각 정점까지의 값

        int maxValue = -1;
        for (int i = 1; i <= n; i++) {
            maxValue = Math.max(maxValue, res[i] + resReverse[i]);
        }
        System.out.println(maxValue);
    }


    public int[] dijkstra(int startPoint, int n, int[][] graph){

        int[] weights = new int[n+1];
        boolean[] visited = new boolean[n+1];
        for(int i=0; i<n+1; i++) {
            weights[i] = Integer.MAX_VALUE;
        }
        weights[startPoint] = 0; // 시작점.

        PriorityQueue<Node> pq = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight));
        pq.add(new Node(startPoint, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int num = node.num;

            if(visited[num]) continue;
            visited[num] = true;

            // num에서 뻗어나가면서 갱신 처리해준다.
            for(int i=1; i<=n; i++){
                if(graph[num][i] == 0) continue; // 값이 없는 경우 계산 불가.
                if(visited[i]) continue; // 방문한 값이면 패스.

                // 현재 점에서 다른 점으로 이동하는 값이 더 작다면 갱신해준다.
                if(weights[num] + graph[num][i] < weights[i] ){
                    weights[i] =  weights[num] + graph[num][i];
                    pq.add(new Node(i, weights[i]));
                }
            }
        }

        return weights;
    }



    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}