[BOJ] 1238. 파티

다익스트라를 활용하는 문제였다.

최단 경로 문제이지만 이 문제는 N의 최대값이 1000이기에 플로이드와샬 기법보다는 다익스트라가 적합할 것 같아서 다익스트라로 접근하였다. 이 문제는 경로가 주어지고 특정 목적지를 왕복하는 문제였다. 따라서 두가지로 나누어 풀어보았다. 첫번째로 시작점에서 목적지까지의 다익스트라, 두번째로 목적지에서 시작점까지의 다익스트라, 이 두가지를 구하여 시작점을 바꿔가며 최대값을 확인하여 답을 풀었다. 즉 max(distanceFromStart[end] + distanceFromEnd[start]) 값을 구하였다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_1238_파티 {
    static class Node implements Comparable<Node> {
        int point;
        int weight;
 
        public Node(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return Integer.compare(weight, o.weight);
        }
    }
 
    static int N;
    static List<Node>[] graph;
    static PriorityQueue<Node> pq;
 
    static int[] d;
    static int[] fromDestination;
    static boolean[] visit;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int destination = Integer.parseInt(st.nextToken());
 
        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList();
        }
 
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            graph[start].add(new Node(end, weight));
        }
 
        d = new int[N + 1];
        visit = new boolean[N + 1];
        pq = new PriorityQueue<>();
 
        for (int i = 1; i <= N; i++) {
            d[i] = Integer.MAX_VALUE / 2;
        }
 
        dijkstra(destination);
 
        fromDestination = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            fromDestination[i] = d[i];
        }
 
        int answer = 0;
 
        for (int i = 1; i <= N; i++) {
            if (i != destination) {
                dijkstra(i);
                // System.out.println(i + ", " + d[destination] + ", " + fromDestination[i]);
 
                answer = Math.max(answer, d[destination] + fromDestination[i]);
            }
        }
 
        System.out.println(answer);
 
    }
 
    static void dijkstra(int i) {
        for (int index = 1; index <= N; index++) {
            visit[index] = false;
            d[index] = (index == i) ? 0 : Integer.MAX_VALUE / 2;
        }
 
        pq.clear();
        pq.add(new Node(i, 0));
 
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
 
            if (visit[cur.point] == true) {
                continue;
            }
 
            for (Node next : graph[cur.point]) {
                if (visit[next.point] == false && d[next.point] > d[cur.point] + next.weight) {
                    d[next.point] = d[cur.point] + next.weight;
                    pq.add(new Node(next.point, d[next.point]));
                }
            }
 
            visit[cur.point] = true;
        }
    }
}