[BOJ/Dijkstra] 백준 1238 - 파티 (Java)

1238 - 파티

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

문제

N개의 숫자로 구분된 각각의 마을에 한 명 학생 살고 있음/ N명의 학생이 X번 마을에 모여서 파티를 벌이기로 함
마을 사이에 총 M개의 단방향 도로가 있고 i번째 길을 지나는데 $T_i$ 시간 소비
파티에 참석하기 위해 걸어가서 다시 마을로 돌아와야 함/ 최단 시간에 오가기
도로는 단방향이기 때문에 오고 가는 길이 다를 수 있음

입력
첫째 줄: N (1 <= N <= 1,000), M (1 <= M <= 10,000), X (1 <= X <= N)
두 번째 줄 ~ M + 1줄: i번째 도로의 시작점, 끝점, 필요한 소요시간 $T_i$
(시작점 != 끝점, 한 도시 A에서 다른 도시 B로 가는 도로의 개수 최대 1개)
출력: N명의 학생들 중 오고 가능데 가장 오래 걸리는 학생의 소요시간

---

풀이

Dijkstra

• 가중치(비용) 있는 그래프에서 한 정점에서 다른 모든 정점까지 최단 경로(가장 적은 비용) 구하는 알고리즘
• BFS는 모든 간선 가중치가 1일 때만 최단 거리 보장
• 지금까지 알고 있는 가장 짧은 거리부터 처리 -> `PriorityQueue`

static class Edge implements Comparable<Edge> {
    int to, time;

    public Edge(int to, int time) {
        this.to = to;
        this.time = time;
    }

    @Override
    public int compareTo(Edge o) {
        return this.time - o.time;
    }
}

 

왕복 시간 = 파티에 가는 최단거리 (i -> X) +  파티에서 집으로 돌아오는 최단거리(X -> i)

• `graph`: 원래 방향 그래프
  • `int[] fromX = dijkstra(graph, X)`
• `reverse`: 뒤집힌 그래프
  • `int[] toX = dijkstra(reverse, X)`

int max = 0;
for (int i = 1; i <= N; i++) {
    max = Math.max(max, fromX[i] + toX[i]);
}

 

`start`에서 출발해서 그래프 `g`의 모든 노드까지 최단거리(`dist`) 계산

• `time > dist[cur]`: 더 긴 경로 버림
• 현재 도시(`cur`)에서 갈 수 있는 모든 도시(`next`)
  • `int nt = time + next.time`: 현재도시까지의 최단거리 + 다음도로로 이동하는 비용
  • `nt < dist[next.to]`: 기존 `dist`와 비교해서 더 짧으면 갱신

static int[] dijkstra(List<List<Edge>> g, int start) {
    int[] dist = new int[N + 1];
    Arrays.fill(dist, INF);

    PriorityQueue<Edge> pQ = new PriorityQueue<>();
    pQ.offer(new Edge(start, 0));
    dist[start] = 0;

    while (!pQ.isEmpty()) {
        Edge cur = pQ.poll();

        if (cur.time > dist[cur.to]) continue;

        for (Edge next : g.get(cur.to)) {
            int nt = cur.time + next.time;

            if (nt < dist[next.to]) {
                dist[next.to] = nt;
                pQ.offer(new Edge(next.to, nt));
            }
        }
    }

    return dist;
}

---

코드

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

// 파티
public class boj_1238 {
    static class Edge implements Comparable<Edge> {
        int to, time;

        public Edge(int to, int time) {
            this.to = to;
            this.time = time;
        }

        @Override
        public int compareTo(Edge o) {
            return this.time - o.time;
        }
    }

    static int N, M, X;
    static List<List<Edge>> graph, reverse;
    static int INF = 1_000_000_000;

    static int[] dijkstra(List<List<Edge>> g, int start) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);

        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.offer(new Edge(start, 0));
        dist[start] = 0;

        while (!pQ.isEmpty()) {
            Edge cur = pQ.poll();

            if (cur.time > dist[cur.to]) continue;

            for (Edge next : g.get(cur.to)) {
                int nt = cur.time + next.time;

                if (nt < dist[next.to]) {
                    dist[next.to] = nt;
                    pQ.offer(new Edge(next.to, nt));
                }
            }
        }

        return dist;
    }

    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());

        graph = new ArrayList<>();
        reverse = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
            reverse.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());

            graph.get(from).add(new Edge(to, time));
            reverse.get(to).add(new Edge(from, time));
        }

        int[] fromX = dijkstra(graph, X);
        int[] toX = dijkstra(reverse, X);

        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, fromX[i] + toX[i]);
        }

        System.out.println(max);
    }
}