[BOJ / 백준] 백준 1238 파티 - (자바 / JAVA)

백준 1238 파티 - JAVA (자바) 

1238번: 파티

 

---

문제

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

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

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

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

예제 입력 :

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

예제 출력 :

10

---

풀이

각각의 학생들은 자신의 마을에서 파티에 참석하기 위해 X마을로 갔다가 자신의 마을로 돌아와야한다.우선 최단 시간에 오고 가기를 원하기 때문에 다익스트라 알고리즘을 사용했다.길은 단방향인데 forward와 reverse 두 개의 인접리스트를 생성한 이유는 다익스트라 알고리즘은 시작점을 기반으로다른 노드로 가는 최단 거리를 구하는 알고리즘이다.그렇기 때문에 forward와 reverse 두 개의 인접리스트를 생성해서 정방향의 그래프와 역방향의 그래프를 저장하고정방향 그래프에서의 시작점을 X번 마을로 둔다면 X번 마을에서 출발해서 각자 마을로 돌아가는데에 가장 가까운 거리를 구할 수 있고,역방향 그래프에서의 시작점을 X번 마을로 둔다면 각자의 마을에서 X번 마을로 가는 최단 거리를 구할 수 있다.

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

public class Main {
    private static class Node {
        int dest;
        int time;

        Node(int dest, int time) {
            this.dest = dest;
            this.time = time;
        }
    }

    private static int N, M, X;
    private static final int INF = Integer.MAX_VALUE;
    private static ArrayList[] forwardAdjList;
    private static ArrayList[] reverseAdjList;
    private static int[] goDist, backDist;

    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());
        forwardAdjList = new ArrayList[N + 1];
        reverseAdjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            forwardAdjList[i] = new ArrayList<>();
            reverseAdjList[i] = new ArrayList<>();
        }

        goDist = new int[N + 1];
        backDist = new int[N + 1];
        Arrays.fill(goDist, INF);
        Arrays.fill(backDist, INF);

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            forwardAdjList[A].add(new Node(B, T));
            reverseAdjList[B].add(new Node(A, T));
        }

        setDist(backDist, forwardAdjList);
        setDist(goDist, reverseAdjList);

        int maxTime = 0;
        for (int i = 1; i <= N; i++) {
            maxTime = Math.max(maxTime, goDist[i] + backDist[i]);
        }
        System.out.println(maxTime);
    }

    private static void setDist(int[] dist, ArrayList[] adjList) {
        PriorityQueue pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.time, o2.time));
        dist[X] = 0;
        pq.add(new Node(X, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            for (Node next : adjList[now.dest]) {
                if (dist[next.dest] > dist[now.dest] + next.time) {
                    dist[next.dest] = dist[now.dest] + next.time;
                    pq.add(new Node(next.dest, dist[next.dest]));
                }
            }
        }
    }
}