[백준] 1162번 - 도로포장 [Java]

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

 

[백준] 1162번 - 도로포장 [Java]

[백준] 1162번 - 도로포장 [Java]

---

1.  아이디어

 

다익스트라 알고리즘과 방문 체크 배열을 포장 횟수에 대해서도 체크하는 방식으로 해결할 수 있다.

---

2. 문제풀이

 

다익스트라 알고리즘의 방문 체크 과정에서 각 도시를 몇 번 포장하고 방문했는지 체크하기 위해 2차원 배열을 활용했다. 거리 배열 역시 포장 횟수에 따라 기록하기 위해 2차원 배열로 설정했다. 이후 현재 도시와 연결된 다른 도시에 대해 포장을 하며 가는 경우와 포장을 하지 않고 가는 경우를 나눠서 다익스트라 알고리즘을 적용했다. 거리의 합이 int형을 넘어가게 돼서 거리 배열 초기화에 주의해야 했다. 추가로 정확히 K번 포장하는게 최단 거리가 아닐 수 있어서 거리 배열을 한번 순회하며 최단 거리를 찾아야 했다.

---

3. 코드

 

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

public class Main {

    private static class Node implements Comparable<Node> {
        int v;
        long w;
        int cnt;

        public Node(int v, long w, int cnt) {
            this.v = v;
            this.w = w;
            this.cnt = cnt;
        }

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

    private static final long INF = 1_000_000_000_000L;

    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());

        List<List<Node>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adj.get(u).add(new Node(v, w, 0));
            adj.get(v).add(new Node(u, w, 0));
        }

        long dist = dijkstra(K, N, adj);
        System.out.println(dist);
    }

    private static long dijkstra(int K, int N, List<List<Node>> adj) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0, 0));

        boolean[][] visited = new boolean[1 + N][1 + K];

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

        while (!pq.isEmpty()) {
            Node node = pq.remove();

            if (visited[node.v][node.cnt]) continue;
            visited[node.v][node.cnt] = true;

            for (Node next : adj.get(node.v)) {

                // 도로를 포장하지 않는 경우
                if (!visited[next.v][node.cnt] && (dist[next.v][node.cnt] > dist[node.v][node.cnt] + next.w)) {
                    dist[next.v][node.cnt] = dist[node.v][node.cnt] + next.w;
                    pq.add(new Node(next.v, dist[next.v][node.cnt], node.cnt));
                }

                // 도로를 포장하는 경우
                if ((node.cnt < K) && !visited[next.v][node.cnt + 1] && (dist[next.v][node.cnt + 1] > dist[node.v][node.cnt])) {
                    dist[next.v][node.cnt + 1] = dist[node.v][node.cnt];
                    pq.add(new Node(next.v, dist[next.v][node.cnt + 1], node.cnt + 1));
                }
            }
        }

        // 정확히 K번 포장하는게 최소가 아닐 수 있음
        long min = INF;
        for (int i = 0; i <= K; i++) {
            if (dist[N][i] == INF) continue;
            min = Math.min(min, dist[N][i]);
        }

        return min;
    }

}

---

4. 후기