[Java] 백준 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개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

예제 출력 1

1

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N, M, K;
	private static ArrayList<Node> [] nodes;
	private static long [][] distance;
	private static long result=Long.MAX_VALUE;
	
	static class Node implements Comparable<Node> {
		int val, cnt;
		long weight;

		public Node(int val, long weight, int cnt) {
			super();
			this.val = val;
			this.weight = weight;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Node [val=" + val + ", weight=" + weight + ", cnt=" + cnt + "]";
		}

		@Override
		public int compareTo(Node o) {
			if(this.weight<o.weight) return -1;
			else if(this.weight==o.weight) return 0;
			else return 1;
		}
		
	}
	
	public static void main(String[] args) throws IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(bf.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		nodes=new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			nodes[i]=new ArrayList<>();
		}
		
		distance=new long[N+1][K+1];
		for(int i=1;i<=N;i++) {
			Arrays.fill(distance[i], Long.MAX_VALUE);
		}
		distance[1][0]=0;
		
		for(int i=0;i<M;i++) {
			st=new StringTokenizer(bf.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			int weight=Integer.parseInt(st.nextToken());
			nodes[start].add(new Node(end, weight, 0));
			nodes[end].add(new Node(start, weight, 0));
		}
		dijkstra();
		
		for(int i=0;i<=K;i++) {
			result=Math.min(result, distance[N][i]);
		}
		System.out.println(result);
	}

	public static void dijkstra() {
		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.add(new Node(1, 0, 0));
		
		while(!pq.isEmpty()) {
			Node now=pq.poll();
			int val=now.val;
			long weight=now.weight;
			int cnt=now.cnt;
			
			if(distance[val][cnt]<weight) continue;
			for(int i=0;i<nodes[val].size();i++) {
				int val2=nodes[val].get(i).val;
				long weight2=nodes[val].get(i).weight+weight;
				
				// 도로 포장을 안 했을 때
				if(distance[val2][cnt]>weight2) {
					distance[val2][cnt]=weight2;
					pq.add(new Node(val2, weight2, cnt));
				}
				
				// 도로 포장을 했을 때
				if(cnt+1<=K && distance[val2][cnt+1]>weight) {
					distance[val2][cnt+1]=weight;
					pq.add(new Node(val2, weight, cnt+1));
				}
			}
		}
		
	}
}

1. 일반적인 다익스트라 문제에서 distance 배열을 2차원으로 바꿔줍니다.

2. distance[i][k] -> i : i번째 도시까지의 걸리는 시간, k : k개의 도로를 포장함

    2-1. 현재 도로를 포장했을 때 : k+1<=K인지 확인하고, distance[i][k+1]에 최단 경로 저장

    2-2. 현재 도로를 포장하지 않았을 때 : 일반적인 다익스트라 방식으로 최단 경로 저장

3. k가 0~K까지일 때 중에서 최단 경로를 찾아줍니다.