[백준] 1162. 도로포장 (Java)

 

🔒 문제

1162번: 도로포장

 

🔑 알고리즘

다익스트라 알고리즘

 

 

💡  풀이

양방향 도로이므로 무방향 그래프이고

정점의 수가 10,000 이고 간선의 수가 50,000*2로 간선의 수가 많지 않으므로 인접 리스트를 이용하였다.

 

1번 도시에서 시작해서 N번 도시까지 가는 최소 비용을 구하는 다익스트라 알고리즘 문제이다.

이때 K번만큼 도로를 포장할 수 있고 포장하면 거리는 0이 된다.

 

예를 들어 K가 2라면, 도시 1에서 도시 2로 갈 때,

여태까지 포장을 한 번도 하지 않은 경우, 한 번 한 경우, 두 번 한 경우 총 3가지의 비용이 생길 것이다.

따라서 이들을 모두 기록하기 위해 기존 다익스트라 알고리즘의 최소 거리를 저장했던 배열 dist[도시 인덱스] 를 dist[도시 인덱스][도로 포장 횟수] 로 확장한다.

dist = new long[N + 1][K + 1];

 

이제 도시를 탐색하며 거리의 비용을 갱신할 때,

도로 포장 횟수가 K 미만이라면,

즉 도로 포장이 가능하다면 도로를 포장했을 때의 최소 거리까지 비교하고 갱신하는 과정을 추가한다.

// 포장하지 않는 경우
if (cur.weight + target.weight < dist[target.id][cur.count]) {
	dist[target.id][cur.count] = cur.weight + target.weight;
	pq.add(new Road(target.id, cur.weight + target.weight, cur.count));
}

// 포장하는 경우
if (cur.count < K && cur.weight < dist[target.id][cur.count + 1]) {
	dist[target.id][cur.count + 1] = cur.weight;
	pq.add(new Road(target.id, cur.weight, cur.count + 1));
}

 

* 도로의 가중치가 최대 1,000,000이고 도로의 개수 N이 최대 10,000 이므로

최악의 경우 도로의 가중치의 합이 Integer의 범위를 넘어가므로 가중치를 담는 부분은 모두 Long 자료형을 사용해야한다.

 

66%에서 틀렸습니다가 나올 경우 dist 배열의 초기화(INF)를 Long.MAX_VALUE 등 충분히 큰 값으로 했는지,

Node 클래스의 가중치를 담은 변수의 자료형이 Long 형인지 확인해보면 된다.

 

 

 

✏️ 코드

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 {
	static long INF = Long.MAX_VALUE;
	static int N, M, K;
	static long dist[][];
	static ArrayList<Road>[] graph;

	public static void main(String[] args) throws NumberFormatException, IOException {
		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());
		graph = new ArrayList[N + 1];
		dist = new long[N + 1][K + 1];

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

		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[A].add(new Road(B, W, 0));
			graph[B].add(new Road(A, W, 0));
		}

		dijkstra(1);

		long min = INF;

		for (int i = 0; i <= K; i++) {
			min = Math.min(dist[N][i], min);
		}
		System.out.println(min);
	}

	static void dijkstra(int start) {

		for (int i = 1; i <= N; i++) {
			Arrays.fill(dist[i], INF);
		}

		PriorityQueue<Road> pq = new PriorityQueue<>();
		pq.add(new Road(start, 0, 0));
		dist[start][0] = 0;

		while (!pq.isEmpty()) {

			Road cur = pq.poll();

			if (dist[cur.id][cur.count] < cur.weight)
				continue;

			for (int i = 0; i < graph[cur.id].size(); i++) {
				Road target = graph[cur.id].get(i);

				// 포장하지 않는 경우
				if (cur.weight + target.weight < dist[target.id][cur.count]) {
					dist[target.id][cur.count] = cur.weight + target.weight;
					pq.add(new Road(target.id, cur.weight + target.weight, cur.count));
				}

				// 포장하는 경우
				if (cur.count < K && cur.weight < dist[target.id][cur.count + 1]) {
					dist[target.id][cur.count + 1] = cur.weight;
					pq.add(new Road(target.id, cur.weight, cur.count + 1));
				}
			}
		}
	}

	static class Road implements Comparable<Road> {
		int id, count;
		long weight;

		public Road(int id, long weight, int count) {
			this.id = id;
			this.weight = weight;
			this.count = count;
		}

		@Override
		public int compareTo(Road o) {
			return weight - o.weight > 0 ? 1 : 0;
		}
	}
}