[백준/Java] 1238

파티

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

문제

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

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

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

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

입력

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

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

출력

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

문제 풀이 방법 및 해설

이번 문제는 다익스트라 문제이다. 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘으로 O(ElgE)의 시간복잡도를 가지고 있다.

문제를 조금 더 분석해보면 1~N 까지의 정점으로부터 X까지의 최소 거리와 X로부터 1~N 까지의 최소거리의 합 에서 제일 큰 값을 반환하는 것이다.

정점이 하나로 정해진 것이 아니기 때문에 2차원 배열을 통해 정점을 기준으로 다른 정점을 가는 최소거리를 저장하였다. 배열의 형식은 [시작지점][목적지점] 으로 이루어져 있다!

풀이 코드

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 {
    public static class Node implements Comparable<Node>{
        int idx, cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[][] answer = new int[N+1][N+1];
        ArrayList<Node>[] lst = new ArrayList[N+1];

        for(int i = 1 ; i <= N ; i++){
            Arrays.fill(answer[i], Integer.MAX_VALUE);
            lst[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            lst[s].add(new Node(e, c));
        }

        for(int i = 1 ; i <= N ; i++) {
            PriorityQueue<Node> pq = new PriorityQueue<>();
            answer[i][i] = 0;
            pq.offer(new Node(i, 0));
            while (!pq.isEmpty()) {
                Node cur = pq.poll();
                if (answer[i][cur.idx] != cur.cost) continue;
                for (Node next : lst[cur.idx]) {
                    if (answer[i][next.idx] > answer[i][cur.idx] + next.cost) {
                        answer[i][next.idx] = answer[i][cur.idx] + next.cost;
                        pq.offer(new Node(next.idx, answer[i][next.idx]));
                    }
                }
            }
        }

        int max = 0;
        for(int i = 1; i <= N ;i++){
            int sum = answer[i][X] + answer[X][i];
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }
}