1800. 인터넷 설치

Problem 💻

결정 문제로 이분탐색 + 다익스트라 or BFS, DFS로 풀 수 있는 문제이다.

컴퓨터 N개를 연결하는 최소 비용을 구하는데, 어떤 비용 X에 대하여 해당 비용 X보다 작으면 돈을 내고, 크면 무료로 연결하여 최소 비용을 구하도록 문제의 요구 조건을 바꾸면 된다.

 

 

Approach 1 ⭕

• 이분탐색 + 다익스트라

이분탐색을 통하여 최소한으로 내야할 금액을 결정하고, 다익스트라를 통해 무료로 연결한 횟수를 가중치로 하여 1 → N 컴퓨터로의 최소 무료 연결 횟수를 구한 다음 해당 횟수가 k를 넘는지 확인하면 된다.

k를 넘는다면 연결할 수 없는 경우이므로 다시 비용을 더 증가시켜보고, k를 넘지 않거나 같다면 비용을 더 줄일 수 있는지를 확인한다. 그렇게해서 예제를 보면 최소 4의 비용은 되어야 1 → N으로 갈 수 있다는 결론이 나온다.

 

Solution 💡

public class BOJ_1800 {

    private static int n, p, k;
    private static ArrayList<ArrayList<Vertex>> graph;

    static class Vertex implements Comparable<Vertex> {
        int v, w;

        public Vertex(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Vertex o) {
            return this.w - o.w;
        }
    }

    public static void main(String[] args) throws IOException {
        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());

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int i = 0; i < p; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph.get(v1).add(new Vertex(v2, w));
            graph.get(v2).add(new Vertex(v1, w));
        }

        int ans = -1;
        int left = 0;
        int right = 1_000_001;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (dijkstra(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }

    private static boolean dijkstra(int x) {
        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        pq.add(new Vertex(1, 0));

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

        while (!pq.isEmpty()) {
            Vertex vertex = pq.poll();

            if (shortest[vertex.v] < vertex.w) continue;
            for (int idx = 0; idx < graph.get(vertex.v).size(); idx++) {
                int nextValue = vertex.w;
                Vertex next = graph.get(vertex.v).get(idx);
                if (next.w > x)
                    nextValue++;
                if (nextValue < shortest[next.v]) {
                    shortest[next.v] = nextValue;
                    pq.add(new Vertex(next.v, nextValue));
                }
            }
        }

        return shortest[n] <= k;
    }
}

 

Reference 📄

https://dlwnsdud205.tistory.com/205

https://justicehui.github.io/usaco/2019/07/12/BOJ1800/