BOJ 1238 파티

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

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 $X (1 ≤ X ≤ N)$번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 $T_i(1 ≤ T_i ≤ 100)$의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

---

입력

첫째 줄에 $N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X$가 공백으로 구분되어 입력된다. 두 번째 줄부터 $M+1$번째 줄까지 $i$번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 $T_i$가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 $X$에 갈수 있고, $X$에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

---

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

---

코드

문제를 읽어보면 구해야 하는 것은 두 가지이다.

1. 특정 마을 A에서 마을 X로 가는 최소 비용
2. 마을 X에서 특정 마을 A로 돌아가는 최소 비용

2번은 시작점이 X로 고정이기 때문에 다익스트라로 충분히 해결 가능하다고 생각했지만, 1번은 시작점이 매번 다른 마을로 변경되기 때문에 다익스트라를 N번 계산해야 한다고 생각했다.

그렇다고 3중 for문으로 구현할 수 있는 플로이드 워셜 알고리즘을 사용하기엔 마을의 수가 1,000개인 case도 있을 수 있기 때문에, 통과하더라도 이 문제의 출제 의도를 벗어났을 거라고 생각했다.

결국, 더 좋은 생각이 안나서 모든 정점에서 매번 다익스트라로 왕복하는데 드는 비용을 계산했고 AC를 받긴 했지만 찝찝해서 다른 블로그들의 코드를 참고했다.

참고한 코드의 아이디어는 다음과 같다.

1) 입력받은 M개의 모든 간선을 방향을 뒤집어 저장하고,
2) 뒤집은 간선 정보로 마을 X에서 특정 마을 A로 가는 최소 비용을 다익스트라로 계산

위와 같이 하면 모든 정점에서 매번 다익스트라로 계산하지 않아도, 각각의 마을에서 마을 X로 가는 최소 비용을 한번의 다익스트라로 계산할 수 있다.

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

public class Main {

    static class Road implements Comparable<Road> {
        int pos, cost;

        public Road(int pos, int cost) {
            this.pos = pos;
            this.cost = cost;
        }

        @Override
        public int compareTo(Road o) {
            return cost - o.cost;
        }
    }

    static int N, M, X;
    static int[] goToParty, backHome; // 마을 i에서 X로 왕래하는 최소 비용 저장을 위한 배열
    static ArrayList<Road>[] roads, reverseRoads; // 간선 정보 저장을 위한 배열

    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());
        goToParty = new int[N + 1];
        backHome = new int[N + 1];
        Arrays.fill(goToParty, Integer.MAX_VALUE);
        Arrays.fill(backHome, Integer.MAX_VALUE);
        roads = new ArrayList[N + 1];
        reverseRoads = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            roads[i] = new ArrayList<>();
            reverseRoads[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()),
                e = Integer.parseInt(st.nextToken()),
                c = Integer.parseInt(st.nextToken());

            roads[s].add(new Road(e, c));
            reverseRoads[e].add(new Road(s, c));
        }

        // 마을 i -> 마을 X로 가는 최소비용 계산
        dijkstra(reverseRoads, goToParty);
        // 마을 X -> 마을 i로 되돌아가는 최소비용 계산
        dijkstra(roads, backHome);

        int max = -1;
        for (int i = 1; i <= N; i++)
            max = Integer.max(max, goToParty[i] + backHome[i]);
        System.out.println(max);
    }

    static void dijkstra(ArrayList<Road>[] roads, int[] minCosts) {
        minCosts[X] = 0; // 시작점 X에서 X로 가는 비용은 0

        PriorityQueue<Road> queue = new PriorityQueue<>();
        queue.offer(new Road(X, 0));
        while (!queue.isEmpty()) {
            Road check = queue.poll();
            for (Road end: roads[check.pos]) {
                if(minCosts[end.pos] < check.cost + end.cost) continue;
                minCosts[end.pos] = check.cost + end.cost;
                queue.offer(new Road(end.pos, check.cost + end.cost));
            }
        }
    }
}