[BOJ] 1238번: 파티 (JAVA)

문제 (Gold 3)

1238번: 파티

풀이

마을들인 N에서 목적지 X까지 걸리는 최단거리 -> A

목적지 X에서 각 마을 N까지 걸리는 최단거리 -> B

를 이용해서 왕복 거리의 최단 거리를 구한다!

B는 출발지로부터 모든 노드까지의 거리를 구하는 다익스트라 알고리즘을 이용

A의 경우, 모든 노드사이의 거리를 구하려는 플로이드 와샬을 이용하려 하였다.

하지만, 플로이드 와샬의 경우 시간초과로 실패!

그렇다면 반대로 생각해서,

모든 경로를 반대로 저장한 후에 출발지 X로부터 각 마을 N까지 걸리는 최단 거리를 구하면 된다!!!!!!

~( 이 부분까지 생각하기가 매우 오래 걸렸다 ㅠㅠ )~

즉, A,B 모두 기본 다익스트라를 통해서 구하면 되는 간단한 문제!

코드

package shortestPath;

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

public class BOJ_1238_파티 {
    static int N,X;
    static List<int[]>[] road;
    static List<int[]>[] road_back;
    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());
        int M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken())-1;
        road = new List[N];      // X에서 N 마을로 가는 경로 판별할 때
        road_back = new List[N]; // N 마을들에서 X로 가는 경로 판별할 때
        for(int i =0 ; i < N ; i++){
            road[i] = new ArrayList<>();
            road_back[i] = new ArrayList<>();
        }
        for(int i =0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken())-1;
            int from = Integer.parseInt(st.nextToken())-1;
            int time = Integer.parseInt(st.nextToken());
            road[to].add(new int[]{from, time});
            road_back[from].add(new int[]{to, time});
        }

        int[] XToN = getDist(road);
        int[] NToX = getDist(road_back);

        int max = 0;
        for(int i =0 ; i < N ; i++){
            max = Math.max(max, XToN[i]+NToX[i]);
        }
        System.out.println(max);
    }

    private static int[] getDist(List<int[]>[] road) {
        int[] dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1[1], o2[1])));
        boolean[] visited = new boolean[N];

        pq.offer(new int[]{X, 0});
        dist[X] = 0;

        while(!pq.isEmpty()){
            int[] cur = pq.poll();

            if(visited[cur[0]]) continue;   // 이미 경로 탐색이 되어있으면 확인할 필요 없음
            visited[cur[0]] = true;

            for(int[] r:road[cur[0]]){
                if(dist[r[0]] > dist[cur[0]] + r[1]){   // 현재 노드를 들렸다 갈 때가 더 빠를 경우
                    dist[r[0]] = dist[cur[0]] + r[1];
                    pq.add(new int[]{r[0], dist[r[0]]});
                }
            }
        }

        return dist;
    }
}