[Java] 백준 1162 - 도로포장

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

1162번: 도로포장

시나리오

- 1번 노드에서 N번 노드로 가는 최소 비용을 구하되 K개 이하의 간선에 비용을 0으로 하는 경우의 수도 존재하므로 노드별 minCost를 담는 배열을 2차원으로 만들어 minCost[노드 번호][도로 포장 개수] 꼴로 저장한다.

- 노드는 최대 10,000 간선은 최대 50,000이 주어지므로 인접리스트를 생성한다. 

- cost는 최대 1,000,000이므로 코스트를 더하다 보면 int범위를 초과할 가능성이 있다. 따라서 cost를 다루는 모든 변수는 long타입으로 선언한다.

정답코드

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

class Main {
    private static int N;
    private static int M;
    private static int K;
    private static List<List<Edge>> adj;
    private static long[][] cost;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        K = Integer.parseInt(input[2]);

        adj = new ArrayList<>(N + 1);
        cost = new long[N + 1][K + 1];
        for (int i = 0; i < N + 1; i++) {
            adj.add(new ArrayList<>());
            Arrays.fill(cost[i], Long.MAX_VALUE);
        }

        for (int i = 0; i < M; i++) {
            String[] temp = br.readLine().split(" ");
            int node1 = Integer.parseInt(temp[0]);
            int node2 = Integer.parseInt(temp[1]);
            int weight = Integer.parseInt(temp[2]);

            adj.get(node1).add(new Edge(node2, weight, 0));
            adj.get(node2).add(new Edge(node1, weight, 0));
        }
        dijkstra();

        System.out.println(calcAnswer());
    }

    private static long calcAnswer() {
       return Arrays.stream(cost[N]).min().getAsLong();
    }

    private static void dijkstra() {
        cost[1][0] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> Long.compare(e1.cost, e2.cost));
        pq.offer(new Edge(1, 0, 0));

        while (!pq.isEmpty()) {
            Edge polled = pq.poll();
            //가지치기
            if (polled.cost > cost[polled.end][polled.cnt]) {
                continue;
            }

            for (Edge current : adj.get(polled.end)) {
                long nextCost = polled.cost + current.cost;
                if (cost[current.end][polled.cnt] > nextCost) {
                    cost[current.end][polled.cnt] = nextCost;
                    pq.offer(new Edge(current.end, nextCost, polled.cnt));
                }
                //cnt가 K보다 작을 때 다음 노드로 가는 간선을 도로포장하는 경우도 추가한다.
                //이 때 해당 간선의 cost는 0이므로 pq.cost는 polled.cost가 들어간다.
                if (polled.cnt < K && polled.cost < cost[current.end][polled.cnt + 1]) {
                    cost[current.end][polled.cnt + 1] = polled.cost;
                    pq.offer(new Edge(current.end, polled.cost, polled.cnt + 1));
                }
            }
        }
    }

    static class Edge {
        int end;
        long cost;
        int cnt;

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

 

도로 포장하는 경우를 고려해 edge클래스에 count필드를 선언하는 아이디어와 다익스트라 로직을 수행하면서 count변수가 k보다 작은 경우 pq에 현재의 가중치는 더하지 않고 삽입하는 아이디어를 떠올렸어야 했다.

그리고 minCost를 2차원 배열로 만드는 아이디어 역시 필요했다.