[자바로 푸는 백준] 1238번 파티

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

1238번: 파티

✅ 골드 Ⅲ

 

🔶 풀이

각 각의 마을에서 파티가 열린 마을 X를 방문했다가 다시 돌아왔을 때 가장 많이 시간을 소비한 학생을 구하라.

 

모든 가중치가 양수이고, 한 정점에서 다른 모든 정점까지의 최단 거리를 구해야하므로 다익스트라.

다익스트라를 두 번 나누어서 해결했다.

 

1. X에서 각 마을까지의 최단 거리

2. 각 마을에서 X까지의 최단 거리 (역방향)

 

위 두가지를 구한 후에 더한 값 중 최대값이 정답이 된다.

 

1번 방법은 X를 출발점으로 두고 다익스트라 알고리즘을 진행해주면 된다.

 

문제는 2번 방법이다.

각 마을마다 다익스트라 알고리즘을 진행하면 효율성이 너무 떨어진다.

때문에 기존 입력값에서 출발 마을과 도착 마을을 반대로 입력해서 한 번의 다익스트라 알고리즘으로 해결할 수 있다.

 

출발 마을과 도착 마을을 반대로 입력함으로써 1번 방법과 동일하게 마을 X를 출발지로 둘 수 있음으로 한 번의 다익스트라 알고리즘으로 최단 거리를 구할 수 있다.

 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, X;
    static int INF = 987654321;
	
    public static class Node implements Comparable<Node> {
        int end, sec;
		
        public Node(int end, int sec) {
            this.end = end;
            this.sec = sec;
        }
		
        public int compareTo(Node o) {
            return this.sec - o.sec;
        }
    }
	
    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());     // 마을 개수
        int M = Integer.parseInt(st.nextToken()); // 도로 개수
        X = Integer.parseInt(st.nextToken());     // 파티가 열리는 마을 번호
		
        ArrayList<Node>[] arrList = new ArrayList[M+1]; // X에서 각 마을로
        ArrayList<Node>[] revList = new ArrayList[M+1]; // 각 마을에서 X로
        for (int i=1; i<=M; i++) {
            arrList[i] = new ArrayList<>();
            revList[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 v = Integer.parseInt(st.nextToken());
			
            arrList[s].add(new Node(e, v));  
            revList[e].add(new Node(s, v));
        }
		
        for (int i=1; i<=M; i++) {
            Collections.sort(arrList[i]);
            Collections.sort(revList[i]);
        }
		
        int[] A = dijkstra(arrList);
        int[] B = dijkstra(revList);
				
        int ans = 0;
        for (int i=1; i<=N; i++) {
            ans = Math.max(ans, A[i] + B[i]);
        }
		
        System.out.println(ans);
    }
	
    public static int[] dijkstra(ArrayList<Node>[] List) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(X, 0));
		
        boolean[] visited = new boolean[N+1];
        int[] dp = new int[N+1];
		
        Arrays.fill(dp, INF);
        dp[X] = 0;
		
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
			
            for (Node next : List[cur.end]) {
                if (!visited[next.end] && dp[next.end] > dp[cur.end] + next.sec) {
                    dp[next.end] = dp[cur.end] + next.sec;
                    pq.add(new Node(next.end, dp[next.end]));
                }
            }
        }		
		
        return dp;
    }
}