[백준] 1238번 - 파티 (Gold 3)

문제 링크

백준 1238번 - 파티 (Gold 3)

문제 설명

N($\leq$ 1,000)개의 마을과 이들 사이를 잇는 M($\leq$ 10,000)개의 단방향 도로들이 있다.
각 도로의 출발지, 도착지, 지나는데 걸리는 시간이 주어져 있다.
각 마을에서 주어진 마을 X까지 갔다가 다시 돌아가는데 걸리는 시간 중 최댓값을 구하시오.

정답 코드 및 설명

마을 X에서 각 마을로 돌아가는 시간은 다익스트라를 통해 쉽게 구할 수 있다.
각 마을에서 X로 가는데 걸리는 시간은 모든 도로를 역방향으로 두고 X에서 시작하는 다익스트라를 통해 구할 수 있다.

만일 모든 (출발지, 도착지) 쌍에 대해 소요 시간을 구함으로써 접근한다면 플로이드-워셜 알고리즘을 사용하게 될텐데, 이렇게 하면 $O(N^3)$이 소요되므로 시간 초과가 발생한다.
하지만 위와 같이 푼다면 모든 도로를 역방향으로 돌리는 시간 $O(M)$과 다익스트라를 두 번 돌리는 시간 $O(M \log M)$만 필요하므로, 전체 시간 복잡도가 $O(M \log M)$이 된다.

시간 복잡도를 정확히 계산하려면 마지막에 왕복 거리의 최댓값을 구하는 과정에 필요한 $O(N)$도 더해주어야하는데, 어차피 $O(N^3)$ 내지는 $O(M \log M)$에 비해 무시할만큼 작은 값이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1238 {
    static final int INF = 2_000_000;
    int n, x;
    int[][] roads;

    void input() throws IOException {
        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;
        setRoads(m, br);
    }

    void setRoads(int m, BufferedReader br) throws IOException {
        roads = new int[n][n];
        StringTokenizer st;
        int start, end;
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken()) - 1;
            end = Integer.parseInt(st.nextToken()) - 1;
            roads[start][end] = Integer.parseInt(st.nextToken());
        }
    }

    int[][] reverse(int[][] roads) {
        int[][] reverse = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                reverse[i][j] = roads[j][i];
            }
        }
        return reverse;
    }

    int[] Dijkstra(int start, int[][] roads) {
        class City {
            final int cityNo;
            final int minTime;

            public City(int cityNo, int minTime) {
                this.cityNo = cityNo;
                this.minTime = minTime;
            }
        }

        int[] minTime = new int[n];
        Arrays.fill(minTime, INF);
        minTime[start] = 0;
        PriorityQueue<City> pq = new PriorityQueue<>(Comparator.comparingInt(c -> c.minTime));
        pq.add(new City(start, 0));
        while (!pq.isEmpty()) {
            City currCity = pq.poll();
            if (minTime[currCity.cityNo] < currCity.minTime) continue;
            for (int i = 0; i < n; i++) {
                if (roads[currCity.cityNo][i] == 0) continue;
                if (minTime[currCity.cityNo] + roads[currCity.cityNo][i] < minTime[i]) {
                    minTime[i] = minTime[currCity.cityNo] + roads[currCity.cityNo][i];
                    pq.add(new City(i, minTime[i]));
                }
            }
        }
        return minTime;
    }

    int max(int start) {
        int[] goingTime = Dijkstra(start, roads);
        int[] returningTime = Dijkstra(start, reverse(roads));
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (max < goingTime[i] + returningTime[i])
                max = goingTime[i] + returningTime[i];
        }
        return max;
    }

    void solution() throws IOException {
        input();
        System.out.println(max(x));
    }

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