[BJ] 1238. 파티

 

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

1238번: 파티

 

✔ 문제 조건

1. N명의 학생(정점), M개의 단방향 도로(간선)이 있다.
2. 학생들은 모두 X번째 마을까지 최단거리로 갔다가 돌아와야 한다.
3. X번째 마을까지 갔다가 돌아오는 시간이 가장 긴 학생의 소요 시간을 출력한다.

✔ 접근 과정

1. 이 문제는 두가지 거리들을 구해야한다. 1) 각 지점에서 X지점까지의 최단거리 2) X지점에서 각 지점까지의 최단거리
2. 단방향 그래프이기 때문에 1) 각 지점에서 X지점까지의 최단거리를 구하려면, 시작점과 도착점이 바뀐 인접행렬을 구해서 시작점을 X라고 두고 각 지점까지의 최단거리 배열 distFrom[]을 구하면 된다. 나는 뒤집힌 인접행렬을 따로 구하지 않고, 다익스트라 알고리즘을 실행할 때 adjMatrix[from][to]에서 행, 렬만 바꾸어서 접근했다.
3. 2) X지점에서 각 지점까지의 최단거리를 구하려면 시작점을 X로 두고 각 지점까지의 최단거리 배열 distFrom[]를 구한다.
4. distFrom[i] + distTo[i]이 합이 최대일 때를 구한다.

 

import java.io.*;
import java.util.*;
// 210625

public class Main_BJ_1238_파티 {
    static int N, M, X;
    static int[][] adjMatrix;
    static int[] distFrom, distTo;

    static class Node implements Comparable<Node> {
        int v, w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.w, o.w);
        }
    }

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        X = stoi(st.nextToken());
        adjMatrix = new int[N+1][N+1];

        distFrom = new int[N+1]; // 각 지점 -> X 지점 최단거리
        distTo = new int[N+1];  // 각 지점 <- X 지점 최단거리
        Arrays.fill(distFrom, Integer.MAX_VALUE);
        Arrays.fill(distTo, Integer.MAX_VALUE);

        for(int i=0; i<M; i++) { // 간선정보
            st = new StringTokenizer(br.readLine(), " ");
            int from = stoi(st.nextToken());
            int to = stoi(st.nextToken());
            int w = stoi(st.nextToken());
            adjMatrix[from][to] = w;
        }

        dijkstra();

        int max = 0;
        for(int i=1; i<=N; i++) {
            if(i==X) continue;
            if(distFrom[i]==Integer.MAX_VALUE || distTo[i]==Integer.MAX_VALUE) continue;
            max = Math.max(max, distFrom[i] + distTo[i]);
        }

        System.out.println(max);

        br.close();
    }

    static void dijkstra() {
        boolean[] v = new boolean[N+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 시작점
        distFrom[X] = 0;
        pq.offer(new Node(X, 0));

        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            if(v[cur.v]) continue;
            v[cur.v] = true;

            for(int i=1; i<=N; i++) {
                if(adjMatrix[i][cur.v]==0) continue;
                if(distFrom[i] > cur.w + adjMatrix[i][cur.v]) {
                    distFrom[i] = cur.w + adjMatrix[i][cur.v];
                    pq.offer(new Node(i, distFrom[i]));
                }
            }
        }

        distTo[X] = 0;
        v = new boolean[N+1];
        pq.offer(new Node(X, 0));
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            if(v[cur.v]) continue;
            v[cur.v] = true;

            for(int i=1; i<=N; i++) {
                if(adjMatrix[cur.v][i]==0) continue;
                if(distTo[i] > cur.w + adjMatrix[cur.v][i]) {
                    distTo[i] = cur.w + adjMatrix[cur.v][i];
                    pq.offer(new Node(i, distTo[i]));
                }
            }
        }

    }

    static int stoi(String str) {
        return Integer.parseInt(str);
    }
}