백준 13907번: 세금 (Java)

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

13907번: 세금

문제

주언이는 경제학을 배워 행상인이 되었다. 두 도시를 오가며 장사를 하는데, 통행료의 합이 가장 적은 경로로 이동하려 한다. 도시들은 양방향 도로로 연결되어있으며, 도로마다 통행료가 존재한다.

그런데 정부는 세금 인상안을 발표하였다. 세금을 한 번에 올리면 문제가 발생할 수 있으므로 여러 단계에 걸쳐서 올린다고 한다. 세금이 A만큼 오르면 모든 도로의 통행료가 각각 A만큼 오르게 된다. 세금이 오르게 되면 주언이가 내야 하는 통행료가 변할 수 있다.

주언이를 도와 초기의 최소 통행료와 세금이 오를 때마다의 최소 통행료를 구하시오.

입력

첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다.

두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D)가 주어진다. 각각 출발 도시와 도착 도시 번호를 의미한다. 도시 번호는 1부터 시작한다.

다음 M개의 줄에는 각각 도로 정보를 나타내는 세 정수 a, b (1 ≤ a < b ≤ N), w (1 ≤ w ≤ 1,000)가 주어진다. 도시 a와 도시 b가 통행료 w인 도로로 연결되어 있다는 것을 의미한다.

다음 총 K개의 줄에는 각각 정수 p (1 ≤ p ≤ 10)가 주어진다. 각각 첫 번째, 두 번째, …, K 번째에 인상되는 세금을 의미한다.

S에서 D로 이동할 수 없는 경우는 주어지지 않는다.

출력

첫 번째 줄에 세금이 오르기 전의 최소 통행료를 출력한다.

두 번째 줄부터 K개의 줄에 각각 첫 번째, 두 번째, …, K 번째 세금이 올랐을 때의 최소 통행료를 출력한다.

 

---

풀이

최소 경로의 길이 하나만 저장하면, 세금을 올릴때마다 얼마나 커지는 지 모른다. 따라서, 이동 횟수와 경로의 길이를 둘 다 저장할 필요가 있다. 하지만, 같은 이동 횟수면 경로의 길이가 짧은 것만 살피면 되기에, 뭔가 두 변수의 변화를 기록할 방법을 생각해보자...

-> 이차원 int 배열 d를 다음과 같이 정의한다: d[i][j]: i번째 도시를 j번 이동하여 방문하는 최소 횟수

i <= N <= 1000이고, j도 마찬가지로 N이하로 잡을 수 있다: N번 이상 이동한다는 것은 중복하여 방문하는 도시가 있다는 뜻인데, 중복하여 방문하는 경로는 무조건 최소 경로가 될 수 없다.

 

이후 다익스트라를 돌린다. 우선순위 큐에서 (위치, 거리, 이동 횟수)를 기록한 'Edge' class를 뺀다. 이후 현재 위치에서 갈 수 있는, 다음에 방문할 위치에 대해 만약 d[방문할 위치][j] (j: 현재 이동 횟수보다 작거나 같은 값)이 현재 이동거리 + 현재 도시와 방문할 도시 간의 거리보다 작다면 --> 이동횟수가 현재 수행하려는 이동횟수보다 적으며, 길이도 짧다는 뜻이니 해당 경로는 무의미한 경로이다.

 

 

효율적인 구현

이후 K+1번동안 세금의 최대를 출력해야 한다. 즉, 최대 N*K <= 3000만번의 단위 연산을 수행해야 한다. 여기서, 'i번째 세금이 증가했을 때 idx번 이동하는 경로가 최소였다면, i+1번째 이후 세금이 증가했을 때 최소 경로는 idx번 이하로 이동하는 경로다'라는, 생각해보면 당연한 아이디어를 적용하면 살짝 더 시간이 줄어든다.

 

 

배운 점

이차원 배열을 선언하는 생각은 들었으나, 이동하는 횟수가 최대 M번이여야 한다고 생각해서 이차원 배열을 선언하면 크기가 3천만이 되어 메모리 초과가 발생할 거라 생각했다. 하지만, 위에서 서술했듯 이동하는 횟수는 최대 N번 이하인 경우만 체크하면 된다.

아직도 다익스트라 내에서 이동 횟수에 대해 for문을 돌면서 체크하는게 효율적인지 Big-O 관점에서는 잘 와닿지가 않는다. 막연하게나마, '유효하지 않은 경로가 우선순위 큐에 들어가지 않도록 하는것이 매우 중요하다' 정도로 이해하면 될 듯하다.

도시 D에서의 최솟값을 찾아야하는데, 막연하게 도시 N으로 적어 시간을 엄청 버렸다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        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 K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Edge(b, w, 1));
            graph.get(b).add(new Edge(a, w, 1));
        }
        
        // (위치, 이동 횟수)별 거리의 최솟값을 담는 이차원 배열
        long[][] d = new long[N+1][N+1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(d[i], Integer.MAX_VALUE);
        }
    
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(S, 0, 0));
        d[S][0] = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (d[cur.loc][cur.cnt]< cur.dist) continue;
            nd: for (Edge nxt: graph.get(cur.loc)) {
                for (int j = 0; j <= cur.cnt; j++) {
                    // 가려는 도시의 거리보다 짧으면서, 이동횟수도 적은 방법이 있는 경우
                    if (cur.dist + nxt.dist > d[nxt.loc][j]) {
                        continue nd;
                    }
                }
                if (d[nxt.loc][cur.cnt+1] > cur.dist + nxt.dist) {
                    d[nxt.loc][cur.cnt+1] = cur.dist + nxt.dist; 
                    pq.offer(new Edge(nxt.loc, d[nxt.loc][cur.cnt+1], cur.cnt + 1));
                } 
            }
        }
        
        
        int[] k = new int[K+1];
        for (int i = 1; i <= K; i++ ) {
            k[i] = Integer.parseInt(br.readLine());
        }
        
        // 효율적인 최솟값 찾기
        int idx = N;
        int tempIdx = 0;
        int kSum = 0;
        for (int i = 0; i < K+1; i++) {
            long min = Long.MAX_VALUE;
            kSum += k[i];
            for (int j = 0; j <= idx; j++) {
                if (min > d[D][j] + j*kSum) {
                    tempIdx = j;
                    min = d[D][j] + j*kSum;
                }
            }
            sb.append(min+"\n");
            idx = tempIdx;
        }
        System.out.println(sb.toString());
    }
 
    static class Edge implements Comparable<Edge> {
        int loc;
        long dist;
        int cnt;
 
        public Edge(int loc, long dist, int cnt) {
            this.loc = loc;
            this.dist = dist;
            this.cnt = cnt;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}