[Gold III][JAVA]백준 1238번:파티

문제

바로가기> [Gold III]백준 1238번:파티

알고리즘 분류

• 그래프 이론
• 데이크스트라
• 최단 경로

조건

• 최단 경로 = 다익스트라!!
• 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
  집에서 파티, 파티에서 집으로 와야함.
  집 -> 파티/ 파티 -> 집

해결방안 (정방향, 역방향의 최단경로를 구해서 더한다)

X = 목적지

모든 모드 -> X
X -> 모든 노드 (다익스트라)

모든 노드가 매번 다르기 때문에 다익스트라를 N번 반복해야한다.
하지만 간선방향을 거꾸로 뒤집어서 X를 출발 노드로 하여 돌리면?
X -> 모든 노드의 거리를 모두 구할 수 있다.

dist1 // 정방향
2 -> 1 까지 최단거리: 1
2 -> 3 까지 최단거리: 3
2 -> 4 까지 최단거리: 7

dist2 // 역방향
2 -> 1 까지 최단거리: 4
2 -> 3 까지 최단거리: 6
2 -> 4 까지 최단거리: 3

정답

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

public class Main {
    static int N, M, X;
    private static List<List<Node>> list, reverseList;
    private static int[] dist1, dist2;

    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()); // 단방향 도로(간선)
        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<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken()); // 출발 노드
            int end = Integer.parseInt(st.nextToken()); // 도착 노드
            int weight = Integer.parseInt(st.nextToken()); // 가중치

            list.get(start).add(new Node(end, weight));
            reverseList.get(end).add(new Node(start, weight));
        }

        dist1 = Dijkstra(list, X); //정방향 (모든 노드 -> X)
        dist2 = Dijkstra(reverseList, X); //역방향 (X -> 모든 노드)

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++)
            max = Math.max(max, dist1[i] + dist2[i]);
        System.out.println(max);
    }

    static public int[] Dijkstra(List<List<Node>> list, int X) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[N + 1];

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

        dist[X] = 0;
        pq.add(new Node(X, 0)); // X에서 시작

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

            if (visited[node.end]) continue;
            visited[cur] = true;

            for (int i = 0; i < list.get(node.end).size(); i++) {
                int next = list.get(cur).get(i).end;
                int weight = list.get(cur).get(i).weight;


                if (dist[next] > dist[cur] + weight) {
                    dist[next] = dist[cur] + weight;
                    pq.add(new Node(next, dist[next]));
                }
            }
        }
        return dist;
    }

    static class Node implements Comparable<Node> {
        int end;
        int weight;

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

        @Override
        public int compareTo(Node o) {
            return weight - o.weight; //weight 오름차순
        }
    }
}