[백준 1238 : JAVA] 파티 / 다익스트라

문제

---

 

 

 

풀이

---

다익스트라 알고리즘의 기본 유형에 해당하는 문제이다.

위 예제를 그래프로 나타내면 아래와 같다.

 

2번 노드를 기준으로 one-to-all 최단거리 비용을 구하는 알고리즘인 다익스트라 알고리즘을 사용해야 한다.

이때, 두 가지 경우가 있다.

1. 파티에 참석하러 가는 경우 (다른 모든 노드들에 대해서 2번 노드로 가는 최단거리)
2. 파티가 끝나고 다시 집으로 돌아오는 경우 (2번 노드에 대해서 다른 모든 노드들에 대한 최단거리)

 

위 두 가지 경우 중, 두 번째 경우는 별다른 고민없이 one-to-all인 다익스트라 알고리즘을 사용하면 된다.

생각해볼 경우는 첫 번째 경우인데, 2번 노드를 목적지로 생각하게 되면 1, 3, 4번 노드 각각에 모두 다익스트라를 사용해야 한다.

이런 비효율적인 방법 대신, 단방향 간선을 반대로 저장하게 되면 마찬가지로 2번 노드를 목적지 노드가 아닌 출발지 노드로 바꿀 수 있다.

 

 

 

코드

---

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

public class Main {

    private static final int INF = 1000000000;

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M, X;
    private static List<List<Node>> list, reverseList;
    private static int[] dist, reverseDist;

    static class Node implements Comparable<Node> {
        int index;
        int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        public int compareTo(Node n) {
            return this.distance - n.distance;
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        reverseList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
            reverseList.add(new ArrayList<>());
        }

        dist = new int[N + 1];
        reverseDist = new int[N + 1];
        Arrays.fill(dist, INF);
        Arrays.fill(reverseDist, INF);

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list.get(u).add(new Node(v, weight));
            reverseList.get(v).add(new Node(u, weight));
        }

        dijkstra(list, dist, X);
        dijkstra(reverseList, reverseDist, X);

        print();
        br.close();
    }

    private static void dijkstra(List<List<Node>> list, int[] distance, int start) {
        boolean[] visited = new boolean[N + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        distance[start] = 0;

        while (!pq.isEmpty()) {
            int idx = pq.poll().index;

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

            for (Node node : list.get(idx)) {
                if (distance[node.index] > distance[idx] + node.distance) {
                    distance[node.index] = distance[idx] + node.distance;
                    pq.add(new Node(node.index, distance[node.index]));
                }
            }
        }
    }

    private static void print() {
        int ans = -1;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dist[i] + reverseDist[i]);
        }
        System.out.println(ans);
    }
}