[BOJ] 백준 [1162] 도로포장 JAVA

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

1162번: 도로포장

문제

풀이

기본적으로 풀이는 우선순위 큐를 이용한 다익스트라 방법이랑 같다. (포장 하지 않을 경우)
하지만 여기선 추가되어야하는 부분이 거리부분인 distance[] 배열을 2차원으로 만드는것이다.

도로포장을 하지않을때 부터(0) 포장했을때(k)까지 의 거리비용이 달라지기 때문
따라서 distance[도시의갯수][도로포장 개수] 로 해야한다 => distance[n+1][k+1]

도로포장을 했을경우랑 하지 않았을 경우인 두 가지의 경우를 큐에 넣어서 탐색을 진행하면 된다.

주의할점 : 주어진 도로의 비용이 1,000,000 까지 나온다. 도로의 수는 10,000 이므로
최악의 경우 Integer의 범위를 넘어가기 때문에 distance 배열의 자료형을 long 형으로 해야한다.

 

import java.util.stream.*;

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;
import static java.util.stream.IntStream.*;

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

public class Main {

    static int n,m,k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        n = input[0]; m = input[1]; k = input[2];

        ArrayList<ArrayList<Node>> road = new ArrayList<>();
        for(int i=0;i<=n;i++) road.add(new ArrayList<>());

        for(int i=1;i<=m;i++){
            input = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();

            road.get(input[0]).add(new Node(input[1],input[2],0));
            road.get(input[1]).add(new Node(input[0],input[2],0)); // 도로 양방향 연결
        } // end input

        System.out.println(findShortPath(1,road));

    }

    static long findShortPath(int start,ArrayList<ArrayList<Node>> road) {

        long[][] distance = new long[n+1][k+1];
        for(int i=0;i<=n;i++)
            Arrays.fill(distance[i],Long.MAX_VALUE);

        distance[start][0]=0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o.weight));
        pq.add(new Node(start,0,0));

        while (!pq.isEmpty()){

            Node cur = pq.poll();

            if(cur.weight > distance[cur.node][cur.cnt])
                continue;

            for (Node next : road.get(cur.node)) {

                //도로를 포장했을경우 => next 노드의 weight 값을 합산 x
                if(cur.cnt<k && distance[next.node][cur.cnt+1] > distance[cur.node][cur.cnt] ){
                    distance[next.node][cur.cnt+1] = distance[cur.node][cur.cnt] ;
                    pq.add(new Node(next.node,distance[next.node][cur.cnt+1],cur.cnt+1));
                }

                //도로를 포장하지 않았을 경우 => next 노드의 weight 값 합산
                if(distance[next.node][cur.cnt] > distance[cur.node][cur.cnt] + next.weight ){
                    distance[next.node][cur.cnt] = distance[cur.node][cur.cnt] + next.weight;
                    pq.add(new Node(next.node,distance[next.node][cur.cnt],cur.cnt));
                }
            }
        }
        
        return Arrays.stream(distance[n]).min().getAsLong();
    }

    static class Node{
        int node,cnt;
        long weight;

        public Node(int node, long weight, int cnt) {
            this.node = node;
            this.cnt = cnt;
            this.weight = weight;
        }
    }
}