문제 Gold 5

문제보기

풀이

이분 탐색 + 다익스트라!

정답이 될 수 있는 값을 이분 탐색으로 정한 후, 검증위해 다익스트라를 활용

이분탐색

1. left는 정답이 될 수 있는 최솟값 0, right는 정답이 될 수 있는 최댓값으로 설정(입력 시, 미리 받아놓음)
2. 중간값으로 다익스트라connectOK()를 돌림
   • 유효하다면, 일단 답으로 설정하고 범위를 좀 더 작은값으로 해서 다시 검사
   • 아니라면, 좀 더 큰 범위에서 다시 검사

✔ 결과값이 0이 될 수 있음을 고려하고, 마지막 출력 조건을 잘 설정하자..!

다익스트라

cost의 기준: K보다 크면 +1의 비용, 아니면 0

+1의 비용을 최대한 안거치는 쪽으로 설정되어 유효한 답이 될 수 있음

💡 dist[N-1] 에는 결국 K보다 큰 비용의 경로를 최소한으로 거쳤을 때, 몇 개를 거쳤는지 알 수 있게 됨

코드

package shortestPath;

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

public class BOJ_1800_인터넷설치 {
    static int N, P, K;
    static List<int[]>[] connect;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        connect = new List[N];
        for(int i = 0 ; i < N ; i++) connect[i] = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        for(int i =0 ; i < P ; i++){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken())-1;
            int f = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken());
            connect[t].add(new int[]{f, c});
            connect[f].add(new int[]{t, c});
            max = Math.max(max, c);
        }

        int left = 0;       // 정답이 될 수 있는 최솟값
        int right = max;    // 정답이 될 수 있는 최댓값
        int res = Integer.MIN_VALUE;
        while(left <= right){   // 종료 조건: 왼쪽 포인터가 오른쪽 포인터보다 크거나 같아질 때
            int mid = (left+right) / 2; // 중간값 설정
            if(connectOK(mid)){ // mid 값이 답이 될 수 있다면
                res = mid;  // 일단 답으로 설정
                right = mid - 1;    // 좀 더 작은 값은 안되는지 다시 검사
            } else{ // 답이 안된다면
                left = mid + 1; // 좀 더 큰 값으로 다시 검사
            }
        }
        System.out.println((res == Integer.MIN_VALUE)?-1:res);
    }

    private static boolean connectOK(int mid) {
        int[] dist = new int[N];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->Integer.compare(o1[1], o2[1]));
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        pq.offer(new int[]{0, 0});

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int n = cur[0];
            int c = cur[1];

            if(dist[n] < c) continue;

            for(int[] i : connect[n]){
                int cost = (i[1] > mid)? c+1 : c;   // K보다 크면 +1, 안크면 0
                if(cost < dist[i[0]]){
                    dist[i[0]] = cost;
                    pq.offer(new int[]{i[0], cost});
                }
            }
        }
        return dist[N-1] <= K;  // dist[N-1] == K보다 큰 비용 경로의 개수
    }
}

제출

result값이 0이 될 수 있다는 것을 고려하지 못했었다..!