[JAVA] 백준 1162 : 도로포장

문제

1162번: 도로포장

 

해결방법

1번에서 N번까지 가는 최소 시간을 출력하는 문제인데,

추가적으로 도로포장이라는 조건이 주어져있다.

 

포장이 가능한 횟수는 K로 주어지고, 포장을 하게 되면 해당 도시를 잇는 도로를 통과하는 시간이 0이 된다.

그래서 기본 다익스트라에 추가적으로 포장횟수를 기록해야 한다.

원래 배열은 dijk[해당 도시까지 최솟값] 을 나타낸다고 하면

이번 문제에서는 dijk[해당 도시까지 최솟값][포장 횟수] 를 사용한 2차원 배열을 이용해준다.

 

또 큐에 넣을 때도 다음 도시로 갈 때 도로를 포장하거나 안 하는 경우 둘 다 가능한지 확인하고 가능하다면 큐에 넣어서 돌려준다.

 

그리고 핵심이 되는 부분은 BFS 방식으로 탐색을 진행하면서

현재 지점에 저장된 최소 시간이 현재 시간보다 적다면 굳이 탐색할 필요 없어서 continue로 넘어가 주는 것이 중요하다.

이걸 하지 않으면 시간 초과가 난다. 그래서 몇 번 실패했다.

 

코드는 아래와 같다.

 

코드

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_G1_1162 {
	
	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());
		
		ArrayList<Road>[] citys = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) citys[i] = new ArrayList<>();
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			// 양방향
			citys[start].add(new Road(end, cost, 0));
			citys[end].add(new Road(start, cost, 0));
		}
		
		long[][] dijk = new long[N + 1][K + 1]; // [해당 도시까지 최솟값][포장 횟수]
		for (int i = 0; i <= N; i++) {
			Arrays.fill(dijk[i], Long.MAX_VALUE);
		}
		
		PriorityQueue<Road> q = new PriorityQueue<>();
		q.offer(new Road(1, 0, K));
		dijk[1][0] = 0;
		
		while (!q.isEmpty()) {
			Road road = q.poll();
			// 현재지점에 저장된 최소시간이 현재 시간보다 적다면 굳이 탐색할 필요없음
			if (dijk[road.end][K - road.canCover] < road.cost) continue;
			
			for (Road cur : citys[road.end]) {
				// 포장안하고 가기
				if (dijk[cur.end][K - road.canCover] > road.cost + cur.cost) {
					dijk[cur.end][K - road.canCover] = road.cost + cur.cost;
					q.offer(new Road(cur.end, dijk[cur.end][K - road.canCover], road.canCover));
				}
				// 포장이 가능하다면 포장하기
				if (road.canCover > 0 && dijk[cur.end][K - road.canCover + 1] > road.cost) {
					dijk[cur.end][K - road.canCover + 1] = road.cost;
					q.offer(new Road(cur.end, dijk[cur.end][K - road.canCover + 1], road.canCover - 1));
				}
			}
		}
		// 여러 포장횟수 중 목적지까지 시간이 제일 최소인 값을 찾음
		long result = Long.MAX_VALUE;
		for (int i = 0; i <= K; i++) {
			result = Math.min(dijk[N][i], result);
		}
		System.out.println(result);
		
	}
	// 시간이 적게드는 순서대로 정렬
	static class Road implements Comparable<Road> {
		int end;
		long cost;
		int canCover; // 포장이 가능한 횟수
		
		Road (int end, long cost, int canCover) {
			this.end = end;
			this.cost = cost;
			this.canCover = canCover;
		}

		@Override
		public int compareTo(Road o) {
			// TODO Auto-generated method stub
			return (int) (cost - o.cost);
		}
	}
}