[백준 1162] 도로포장 (Dijkstra, 다익스트라)

🧐 백준 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보다 작거나 같은 자연수이다.

예제

예제 입력	예제 출력
4 4 1 1 2 10 2 4 10 1 3 1 3 4 100	1

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

1162번: 도로포장

 

💡 문제 풀이

단순한 다익스트라 알고리즘으로는 풀리지 않는 문제였다. 최단 거리 배열을 업데이트 할 때마다 경로를 리스트 형식으로 저장해주는 등 여러 방법을 생각해봤지만 풀이 중간에 한 번씩은 막히는 방법들이었다. 결국 구글링을 통해 찾아보니 DP를 함께 사용해서 풀 수 있는 문제였다.

 

단순 다익스트라 유형과는 다르게 Edge 클래스를 정의한다. 해당 클래스는 현재 지점, 도로 포장 개수, 총 거리 비용 정보를 포함한다.

또한, cost 기준으로 오름차순 정렬될 수 있도록 compareTo 메소드도 오버라이드 해준다.

static class Edge implements Comparable<Edge> {
	int end; // 도착(현재) 지점
	int count; // 도로 포장 개수
	long cost; // 총 거리 비용

	Edge(int end, int count, long cost) {
		this.end = end;
		this.count = count;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

 

다음은 초기화 단계이다.

도로 정보를 저장하는 edges, k개 도로를 포장하고 i번 지점까지 가는 데 걸리는 최단 거리 비용을 저장하는 dp를 초기화 한다.

List<List<Edge>> edges = new ArrayList<>(); // 도로 정보
long[][] dp = new long[N + 1][K + 1]; // dp[i][k] : k개 도로를 포장해서 i번 지점까지 가는 최단 거리 비용

// edges, dp 초기화
for (int i = 0; i <= N; i++) {
	edges.add(new ArrayList<>());
	Arrays.fill(dp[i], Long.MAX_VALUE);
}

for (int i = 0; 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());
	edges.get(v1).add(new Edge(v2, 0, c));
	edges.get(v2).add(new Edge(v1, 0, c));
}

 

초기화 후 다익스트라 알고리즘을 실행하며 dp 배열을 업데이트 시켜준다.

Queue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(1, 0, 0)); // 서울 지점, 포장 개수 0, 거리 0
dp[1][0] = 0; // 0개 도로 포장하고 1번(서울) 지점까지

while (!pq.isEmpty()) {
	Edge now = pq.poll();
	if (dp[now.end][now.count] < now.cost) continue;
	for (Edge next : edges.get(now.end)) {
		if (dp[next.end][now.count] > now.cost + next.cost) {
			dp[next.end][now.count] = now.cost + next.cost;
			pq.add(new Edge(next.end, now.count, dp[next.end][now.count]));
		}

		if (now.count < K && dp[next.end][now.count + 1] > now.cost) {
			dp[next.end][now.count + 1] = now.cost;
			pq.add(new Edge(next.end, now.count + 1, now.cost));
		}
	}
}

우선순위 큐를 사용하여 cost 값이 작은 순서대로 처리한다. (여기서 dp 값이 now.cost 보다 이미 작으면 넘어간다.)

도로를 사용하여 넘어간 지점의 dp 값을 2가지 경우로 업데이트 시켜준다.

첫번째는 도로를 포장하지 않고 넘어가는 경우이다.

도로를 포장하지 않았으므로 넘어가면 now.cost + next.cost 만큼의 거리 비용이 발생한다. dp 값이 해당 거리 비용보다 크면 최솟값으로 해주고, 우선순위 큐에 다음 Edge 정보를 추가한다.

두번째는 도로를 포장하고 넘어가는 경우이다.

먼저 도로를 포장할 수 있는 조건인지 확인한다. 이미 포장한 도로의 개수가 K보다 작으면(now.count < K) 포장할 수 있다.

도로를 포장하므로 0의 비용으로 넘어가고 now.cost 만큼의 거리 비용이 발생한다. dp 값보다 작은 비용이면 dp 값을 최솟값으로 업데이트 해주고, 우선순위 큐에 다음 Edge 정보를 추가한다. 도로를 포장했으므로 count 값은 now.count + 1이 된다.

 

마지막으로 N번 지점(포천)까지 갈 수 있는 최소 거리 비용을 구한다.

long min = Long.MAX_VALUE;
for (long cost : dp[N]) {
	min = Math.min(min, cost);
}

dp[N][0] ~ dp[N][K] 값 중에서 최솟값을 구한다.

 

위 풀이 방식을 전체 코드로 풀어내면 다음과 같다.

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

public class Main {

	static class Edge implements Comparable<Edge> {
		int end; // 도착(현재) 지점
		int count; // 도로 포장 개수
		long cost; // 총 거리 비용

		Edge(int end, int count, long cost) {
			this.end = end;
			this.count = count;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return Long.compare(this.cost, o.cost);
		}
	}

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

		List<List<Edge>> edges = new ArrayList<>(); // 도로 정보
		long[][] dp = new long[N + 1][K + 1]; // dp[i][k] : k개 도로를 포장해서 i번 지점까지 가는 최단 거리 비용

		// edges, dp 초기화
		for (int i = 0; i <= N; i++) {
			edges.add(new ArrayList<>());
			Arrays.fill(dp[i], Long.MAX_VALUE);
		}

		for (int i = 0; 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());
			edges.get(v1).add(new Edge(v2, 0, c));
			edges.get(v2).add(new Edge(v1, 0, c));
		}

		// dijkstra
		Queue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(1, 0, 0));
		dp[1][0] = 0;

		while (!pq.isEmpty()) {
			Edge now = pq.poll();
			if (dp[now.end][now.count] < now.cost) continue;
			for (Edge next : edges.get(now.end)) {
				if (dp[next.end][now.count] > now.cost + next.cost) { // 도로 포장 X
					dp[next.end][now.count] = now.cost + next.cost;
					pq.add(new Edge(next.end, now.count, dp[next.end][now.count]));
				}

				if (now.count < K && dp[next.end][now.count + 1] > now.cost) { // 도로 포장
					dp[next.end][now.count + 1] = now.cost;
					pq.add(new Edge(next.end, now.count + 1, now.cost));
				}
			}
		}

		long min = Long.MAX_VALUE;

		for (long cost : dp[N]) {
			min = Math.min(min, cost);
		}

		System.out.println(min);

	}
}

Reference

https://velog.io/@dls4585/%EB%B0%B1%EC%A4%80-1162-%EB%8F%84%EB%A1%9C%ED%8F%AC%EC%9E%A5-JAVA

 

✨ 포스팅을 마치며

다익스트라에 DP 유형까지 섞여서 정답 풀이를 보고 이해하는 데도 시간이 꽤 들었다. 참신한 문제였다고 생각한다. 🤩