백준 13907 (세금) - java

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

13907번: 세금

 

문제

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

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

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

 

유형 : 다익스트라 + 다이나믹 프로그래밍

 

접근 방식

• 세금이 오르는 횟수 K번만큼 다익스트라를 수행한다면 시간 초과를 맛보게 될 것이다.
• 이 문제를 해결하는 핵심 전략은 다익스트라는 1번만 수행한다는 것이다. 
  • 다익스트라를 1번만 수행하기 위해 중요한 접근은 다이나믹 프로그래밍과 결합하는 것이다.
• dis[i][j] 배열을 선언하자 : i번째 지점에 j개의 노드를 거쳐서 왔을 때의 최소 통행료
• 세금은 모든 간선에 대해 증가한다. 즉 기존 최소값 + (간선의 개수 * 해당 차례의 증가량)을 고려해야 한다는 것이다.

전체 코드

package Implementation_BruteForce;

import java.util.*;
import java.io.*;

public class BOJ_13907_세금 {
    static int n,m,k,s,d;
    static int[][] dis;
    static int[] up;
    static ArrayList<Node>[] graph;

    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());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()," ");
        s = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[v1].add(new Node(v2,c,0));
            graph[v2].add(new Node(v1,c,0));
        }

        up = new int[k+1];
        for(int i = 1 ; i <= k ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int tmpNum = Integer.parseInt(st.nextToken());
            up[i] = tmpNum;
        }

        search();

        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i <= k  ; i++){
            int curUp = up[i];
            int max = Integer.MAX_VALUE;

            for(int j = 1 ; j <= n ; j++){

                if(dis[d][j] == Integer.MAX_VALUE)
                    continue;

                int upper = (j - 1) * curUp;

                dis[d][j] += upper;

                max = Math.min(max,dis[d][j]);
            }

            sb.append(max+"\n");
        }

        System.out.print(sb);
        br.close();
    }

    static void search(){
        dis = new int[n+1][n+2]; // i번째 지점에 j개의 간선을 딛고 온 경으
        for(int i = 1 ; i <= n ; i++){
            for(int j = 0 ; j <= n ; j++){
                dis[i][j] = Integer.MAX_VALUE;
            }
        }

        for(int i = 0 ; i <= n ; i++){
            dis[s][i] = 0;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        pq.add(new Node(s,0,1));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.v == d){
                continue;
            }

            if(dis[cur.v][cur.count] < cur.c)
                continue;

            for(Node next : graph[cur.v]){
                int nextC = cur.c + next.c;
                int nextCount = cur.count + 1;

                if(dis[next.v][nextCount] > nextC){
                    dis[next.v][nextCount] = nextC;
                    pq.add(new Node(next.v,nextC,nextCount));
                }

                for(int tmpC = nextCount + 1 ; tmpC <= n ; tmpC++){
                    if(dis[next.v][tmpC] > nextC){
                        dis[next.v][tmpC] = nextC;
                    }
                }
            }
        }
    }



    static class Node{
        int v;
        int c;
        int count;

        Node(int v,int c,int count){
            this.v = v;
            this.c = c;
            this.count = count;
        }
    }
}