[백준] 1162번 : 도로 포장

1162번: 도로포장

# 문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

# 입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

 #출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

# 예제 입력

4 4 1

1 2 10

2 4 10

1 3 1

3 4 100

# 예제 출력

1

---

[Dijkstra + Dynamic Programming]

백준 문제 중에 '벽 부수고 이동하기' 시리즈의 문제가 있다. 그 문제와 약간 비슷한 맥락인 문제이다.

 

2차원 배열 distance[10001][21]을 준비한다. 시작 정점 1에서 정점 i까지 가는데 0개의 도로를 포장하여 갈 때, 1개의 도로를 포장하여 갈 때, 2개의 도로를 포장하여 갈 때, ..., K개의 도로를 포장하여 갈 때를 메모제이션 해주는 것이다.

 

그래서 일반 다익스트라 처럼 우선 순위 큐를 쓰되, 우선 순위 큐의 원소로 들어가는 것은 (정점, 가중치, 도로 포장 개수)이다.

 

Dijkstra(int start)
{
	우선순위 큐 pq;
	distance[start][0] = 0; //시작 정점, 그리고 도로 포장을 0개 했을 때의 거리 = 0
    pq.enqueue(start, 0, 0);
    
    while(!pq.isEmpty()){
    
    	int current = pq.peek().target;
        int dist = pq.peek().dist;
        int cnt = pq.peek().cnt;
        
        pq.poll();
        
        if(distance[current][cnt] < dits) continue;
        
        for(Edge e : list[current]){
        	int next = e.target;
            int nextDist = dist + e.dist;
            
            if(distance[next][cnt] < nextDist){
            	distance[next][cnt] = nextDist;
                pq.enqueue(next, nextDist, cnt);
            }
            
            if(cnt < K && distacne[next][cnt + 1] < dist){
            	distance[next][cnt + 1] = dist;
                pq.enqueue(next, dist, cnt + 1);
            }
       }
   }
}
    

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int tg, cnt;
        long d;
        public Edge(int t, long dt, int cnt){
            tg = t;
            d = dt;
            this.cnt = cnt;
        }
        @Override
        public int compareTo(Edge o) {
            if(d > o.d) return 1;
            else if(d < o.d) return -1;
            return 0;
        }
    }
    static final long INF = Long.MAX_VALUE;
    static final int N = 10001;
    static List<Edge>[] list = new ArrayList[N];
    static long[][] distance = new long[N][21];

    static void Dijkstra(int start, int k){

        Queue<Edge> pq = new PriorityQueue<>();
        distance[start][0] = 0;
        pq.add(new Edge(start, 0, 0));

        while (!pq.isEmpty()){
            Edge edge = pq.poll();
            int current = edge.tg;
            long d = edge.d;
            int cnt = edge.cnt;

            if(distance[current][cnt] < d) continue;

            for(Edge e : list[current]){
                int next = e.tg;
                long nextD = d + e.d;

                if(distance[next][cnt] > nextD){
                    distance[next][cnt] = nextD;
                    pq.add(new Edge(next, nextD, cnt));
                }

                if(cnt < k && distance[next][cnt + 1] > d){
                    distance[next][cnt + 1] = d;
                    pq.add(new Edge(next, d, cnt + 1));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        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());

        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
            Arrays.fill(distance[i], INF);
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int home = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());

            list[home].add(new Edge(target, dist, 0));
            list[target].add(new Edge(home, dist, 0));
        }

        Dijkstra(1, k);

        long min = INF;
        for(int i=0; i<=k; i++)
            min = Math.min(min, distance[n][i]);

        System.out.println(min);
    }
}