[백준 JAVA] 1238번: 파티

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

 

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

public class Main {
    public static int N, M, X, ans;
    public static int[] fromX, toX;
    public static List<int[]>[] graph, revGraph;
    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());
        X = Integer.parseInt(st.nextToken());
        ans = Integer.MIN_VALUE;
        graph = new List[N + 1];
        revGraph = new List[N + 1];
        for(int i = 1; i < N + 1; i++){
            graph[i] = new ArrayList<>();
            revGraph[i] = new ArrayList<>();
        }

        // 1. 그래프 입력받기
        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 w = Integer.parseInt(st.nextToken());
            graph[u].add(new int[] {v, w});
            revGraph[v].add(new int[] {u, w});
        }

        // 2. X에서 각 노드 까지, 각 노드에서 X까지 최단거리 탐색
        fromX = dijkstra(graph, X);
        toX = dijkstra(revGraph, X);

        // 3. 결과 합치기
        for(int i = 1; i < N + 1; i++){
            int cur = fromX[i] + toX[i];
            ans = Math.max(cur, ans);
        }

        // 4. 최대값 출력
        System.out.println(ans);

    }
    public static int[] dijkstra(List<int[]>[] g, int start){
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        pq.offer(new int[] {start, 0});

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int now = cur[0];
            int nowDist = cur[1];
            if(nowDist > dist[now]) continue;

            for(int[] next : g[now]){
                int cost = next[1] + nowDist;
                if(dist[next[0]] > cost){
                    dist[next[0]] = cost;
                    pq.offer(new int[] {next[0], cost});
                }
            }
        }

        return dist;
    }
}

 

정방향으로 X에서 각 노드까지의 최단을 구하는건 다익스트라를 이용해서 쉽게 풀었지만

 

각 노드에서 X까지의 최단을 구하는것이 좀 어려웠다.

 

아이디어는 GPT를 통해 얻었으며 그래프를 뒤집어서 최단을 구하면 그것이 바로 각 노드에서 X까지의 최단이라는 힌트를 얻었다.

 

기존에 다익스트라 함수를 분리하고 dist, graph를 두개를 둬서 마지막에 합쳐서 최대를 구하는 방식으로 풀이하였다.