[BOJ] 백준 [1800] 인터넷 설치 JAVA

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

1800번: 인터넷 설치

📝문제

📝풀이

처음 풀어보는 유형의 문제다. 아이디어를 못 떠올려서 도움을 받았다..

만약 1-3-2-5 이런식으로 연결 된다고 치면 각각 edge들에 대하여 가중치들은 4, 3, 9 원이다.
여기서 k=1, 회선 하나는 공짜로 준다고 했으니 제일 비싼 9원을 빼면 남은건 4, 3 인데
이들 중 제일 비싼 회선 값만 return 하므로 ans=4 이 답이다

일단 출발점(1) 에서 부터 출발해서 탐색을 진행하는데 도착지(n) 까지
제일 싼 간선을 생각하면서 가야하므로 다익스트라 알고리즘을 사용한다

그런데 회선 몇개 까지 공짜로 봐주는지 체크를 해 가며 가야하므로 경우의 수가 너무 많다
그래서 특정 목표 추정치 Estimate 를 기준으로 도달 가능한지에 대한 여부로 범위를 좁혀가야 한다.

거기다가 가중치의 합 이라는 개념이 필요가 없다
그러므로 거리배열 Dist[] 의 정의를 공짜 회선으로 전환한 갯수로 하였다

그래서 최종적으로 Dist[n] 의 값이 K 안에 있으면 도달 가능한지에 대한 여부를 반환하면서
이분탐색으로 도달가능하면 mid값 낮추고 도달 불가능하면 mid 값 높히는 식으로 답을 도출해야 한다. 

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

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    static int n,e,k;
    static int minEstimate=0,maxEstimate;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    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]; e = input[1]; k = input[2];

         for(int i=0;i<=n;i++)
             graph.add(new ArrayList<>());
         for(int i=0;i<e;i++){
             input = stream(br.readLine().split(" "))
                     .mapToInt(Integer::parseInt).toArray();
             graph.get(input[0]).add(new Node(input[1],input[2]));
             graph.get(input[1]).add(new Node(input[0],input[2]));
             maxEstimate = Math.max(maxEstimate,input[2]);
         }//end input

        int ans=-1;

        while (minEstimate<=maxEstimate){ //이분 탐색
            int midEstimate = (minEstimate+maxEstimate)/2;

            if(isArrive(midEstimate)) { //도달 가능하면 ans 갱신
                ans = midEstimate;
                maxEstimate = midEstimate - 1; // max 추정치 범위를 좁힘
            }
            else
                minEstimate = midEstimate + 1; // min 추정치 범위를 좁힘
        }
        System.out.println(ans); // 도달 불가능이면 -1
    }
    static boolean isArrive(int estimate){ // 추정치로 탐색 가능한지 탐색

        int[] dist = new int[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[1]=0;

        PriorityQueue<Node> pq = new PriorityQueue<Node>((o1, o2) -> o1.weight-o2.weight);
        pq.add(new Node(1,0));

        while (!pq.isEmpty()){
            Node cur = pq.poll();

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

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

                int nextCount=cur.weight; // 공짜회선 개수

                if(estimate < next.weight) // 더 비싼 회선가격이 나오면
                    nextCount++; // 공짜 회선으로 전환

                if(dist[next.node] > nextCount){
                    dist[next.node]=nextCount;
                    pq.add(new Node(next.node,nextCount));
                }
            }
        }

        return dist[n]<=k; // 공짜회선 k개 보다 적은 개수이면 탐색 가능
    }
    static class Node {
        int node,weight;

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