자바(백준) 1238 파티

오답 노트 & 새로 알게 된 점

해당 문제는 풀이 방법이 두 가지 있다.

첫 번째 방법은 생각하기 쉽지만 시간 복잡도가 다른 방법에 비해 크고,

다른 방법은 와 이걸 이렇게도 풀구나 하면서(나만 그럴 수 있음) 시간 복잡도가 첫 번째 방법에 비해 작다.

 

첫 번째 풀이

일반적으로 다익스트라를 사용한다. 

다만 문제에서 출발할 때의 최소 경로 + 복귀할 때의 최소 경로 중 최댓값을 구하라했다.

일반적으로 나는 이와 같은 문제를 풀 때 다익스트라를 모든 정점에서 구한다(N번)

예제에서 start가 1, 3, 4 (2는 파티정점이므로 제외) 일 때 다익스트라를 구하여 각각 dist[X] 값을 더해주고,

또 start가 2일 때 다익스트라를 구하여 각각 dist[N] 을 더해주었다. 그리고 이 중에 최댓값을 구해줬다.

 

해당 풀이는 시간 복잡도가 N^2logN으로 아래와 같은 시간이 나왔다.

 

 

두 번째 풀이

두 번째 풀이는 정말 신기했다.

처음 풀이보다 시간 복잡도가 3배나 줄게 된다.

예제를 그림으로 표현하면 복귀 부분이다.

하지만 입력에서 반대로 가는 경로도 저장해준다.

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

    A[from].add(new Node(to, wei));
    B[to].add(new Node(from, wei));
}

이렇게 되면 파티하는 정점에서의 다익스트라를 구하게 되면 출발, 복귀하는 최소 경로를 NlogN에 찾을 수 있다.

즉, 1번 풀이에서는 다익스트라를 N번 반복했지만, 해당 풀이는 2번의 다익스트라를 실행하면 된다.

 

어떻게 이렇게 풀 수 있을까?

 

우리가 구해야할 것은

 

1. 각 정점마다 X까지의 최소경로

2. X에서 출발하여 각 정점까지의 최소경로이다.

다익스트라는 한 정점에서 모든 정점까지의 최소 경로를 구하는 알고리즘이다.

2번은 우리가 일반적으로 풀었던 다익스트라로 풀면 금방 구한다.

 

1번 풀이는 다익스트라를 N번 돌려야 알 수 있는 값이다.

( 1번에서 다익 구한 뒤 dist[X], 2번에서 다익 구한 뒤 dist[X] ...)

하지만 문제에서 단방향이라고 했으므로 문제에서 주어진 from과 to를 바꿔서 X에서 출발한다고 생각한다.

X를 출발점으로 하고 각 정점의 최소경로를 구하면 한 번에 구해지는 것을 알 수 있다.

 

 

---

코드 1

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M, X;
    static ArrayList<Node> A[];
    static int dist[];
    static int ans[];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        for (int i = 1; i <= N; i++) {
            if(i == X) continue;
            dijkstra(i);
            ans[i] += dist[X];
        }
 
        dijkstra(X);
        for (int i = 1; i <= N; i++) {
            if(i == X) continue;
            ans[i] += dist[i];
        }
 
        int max = Integer.MIN_VALUE;
 
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, ans[i]);
        }
 
        System.out.println(max);
    }
 
    static void dijkstra(int start) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Info> pq = new PriorityQueue<>((o1, o2)->{
            return o1.dist - o2.dist;
        });
 
        pq.offer(new Info(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Info info = pq.poll();
 
            for (Node n : A[info.idx]) {
 
                if(dist[info.idx] != info.dist) continue;
 
                if(dist[info.idx] + n.wei >= dist[n.to]) continue;
 
                dist[n.to] = dist[info.idx] + n.wei;
                pq.offer(new Info(n.to, dist[n.to]));
            }
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
        X = atoi(st.nextToken());
 
        A = new ArrayList[N + 1];
        dist = new int[N + 1];
        ans = new int[N + 1];
 
        for (int i = 0; i <= N; i++) A[i] = new ArrayList<>();
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
            int wei = atoi(st.nextToken());
 
            A[from].add(new Node(to, wei));
        }
    }
 
    static class Node{
        int to, wei;
 
        public Node(int to, int wei) {
            this.to = to;
            this.wei = wei;
        }
    }
 
    static class Info{
        int idx, dist;
 
        public Info(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }
}