[JAVA] 백준 20168 - 골목 대장 호석 - 기능성

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

가지고 있는 돈 이내로 갈 수 있는 경로 중 최댓값의 최솟값을 구하는 문제이다.

얼마전 풀었던 인터넷 설치 문제와 굉장히 유사해 바로 이분탐색을 생각하게 되었다.

https://ghcode.tistory.com/286

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

0 ~ 가지고 있는 돈 사이를 이분탐색 하되, mid값을 초과하는 가중치에 대해서는 가지고 있는 돈 + 1로 치환하고, 해당 조건으로 끝까지 갈 수 있을 경우에 저장하고 있던 max값의 min값을 누적해 마지막에 출력했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int vertexCount = info[1];
        int start = info[2];
        int end = info[3];
        int budget = info[4];

        int[] dist = new int[nodeCount + 1];
        boolean[] visited = new boolean[nodeCount + 1];

        List<List<Street>> list = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < vertexCount; i++) {
            int[] street = getArray(br.readLine());
            list.get(street[0]).add(new Street(street[1], street[2]));
            list.get(street[1]).add(new Street(street[0], street[2]));
        }


        int left = 0;
        int right = budget;
        int answer = Integer.MAX_VALUE;
        while (left <= right) {
            int maxCost = 0;
            int mid = (left+right)/2;
            visited = new boolean[nodeCount + 1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[start] = 0;
            N20168 add = new N20168(start);
            PriorityQueue<N20168> pq = new PriorityQueue<>();
            pq.offer(add);
            while (!pq.isEmpty()) {
                N20168 target = pq.poll();
                int v = target.value;
                int weight = dist[v];
                if (visited[v]) continue;
                visited[v] = true;
                List<Street> sList = list.get(v);
                if(v==end){
                    maxCost = Math.max(maxCost, target.maxCost);
                }
                for (int i = 0; i < sList.size(); i++) {
                    Street s = sList.get(i);
                    int to = s.to;
                    int cost = s.cost>mid?budget+1:s.cost;
                    if (dist[to] > weight + cost // 더 싸면
                            && weight + cost <= budget // 예산 이내의 경로이면
                    ) {
                        dist[to] = weight + cost;

                        N20168 offer = new N20168(to);
                        offer.maxCost = Math.max(target.maxCost, cost);
                        offer.weight = weight + cost;
                        pq.offer(offer);
                    }
                }
            }
            if(dist[end]==Integer.MAX_VALUE){ //최댓값이 mid인 다익스트라로 경로에 도달 못했을 때
                left = mid+1;
            }else{//최댓값이 mid인 다익스트라로 경로에 도달 했을 때
                right = mid-1;
                answer = Math.min(answer, maxCost);
            }
        }
        System.out.println(answer==Integer.MAX_VALUE?-1:answer);
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }

}

class N20168 implements Comparable<N20168> {
    int value;
    int weight = 0;
    int maxCost = Integer.MIN_VALUE;

    N20168(int v) {
        this.value = v;
    }

    @Override
    public int compareTo(N20168 o) {
        return this.weight - o.weight;
    }
}

class Street {
    int to;
    int cost;

    Street(int t, int c) {
        this.to = t;
        this.cost = c;
    }
}