[백준/Java] 1238 : 파티

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

 

이번 문제는 다익스트라 문제입니다. 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘으로 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 Backjoon_1238_파티 {
    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);
    }
}