[백준] 1800. 인터넷 설치

문제 링크

[백준] 1800. 인터넷 설치

풀이 과정

처음 문제 접근은 dfs 탐색을 이용했습니다. 1번 컴퓨터에서 시작해 각 컴퓨터를 이동하며 가격들을 리스트에 저장해두고, N번 컴퓨터에 도착하면 리스트를 오름차순으로 정렬한 뒤에 뒤에서 (K+1) 번째 가격을 답으로 출력했습니다. K개의 케이블은 공짜니까, 비싼 것부터 K개를 제외하려는 접근은 O((V+E)ElogE) 의 시간복잡도를 가지며, 이로 인해 시간초과가 발생했습니다.

시간 안에 정답을 구하기 위해서는 답을 미리 정해두고 풀어야 합니다. 예를 들어, K가 1일 때 케이블의 가격 4가 정답이다고 결정을 내리면, 경로상에 가격이 4보다 큰 케이블의 개수가 K개가 넘어가면 해당 답은 모순이 되므로 정답이 아니게 됩니다.

1번 컴퓨터를 시작으로 인접한 컴퓨터들을 지나 N번 컴퓨터에 도착하기까지 사용된 최소 무료 케이블의 수를 구하기 위해 다익스트라 알고리즘을 적용했습니다.

코드

import java.util.*;

public class Main {
    static int N, P, K;
    static List<Edge>[] adj;
    static final int INF = 1000000;
    static int answer = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        P = sc.nextInt();
        K = sc.nextInt();

        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++)
            adj[i] = new ArrayList<>();

        for (int i = 0; i < P; i++) {
            int v1, v2, cost;
            v1 = sc.nextInt();
            v2 = sc.nextInt();
            cost = sc.nextInt();

            adj[v1].add(new Edge(v2, cost));
            adj[v2].add(new Edge(v1, cost));
        }

        int left = 0, right = INF;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (dijkstra(mid)) {
                right = mid - 1;
                answer = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(answer);
    }

    public static boolean dijkstra(int mid) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(1, 0));

        while (!pq.isEmpty()) {
            Edge now = pq.poll();

            if (now.cost > dist[now.vertex]) continue;

            for (Edge next : adj[now.vertex]) {
                int cost = (next.cost > mid) ? 1 : 0;

                if (dist[next.vertex] > now.cost + cost) {
                    dist[next.vertex] = now.cost + cost;
                    pq.add(new Edge(next.vertex, dist[next.vertex]));
                }
            }
        }

        return dist[N] <= K;
    }

    static class Edge implements Comparable<Edge> {
        int vertex;
        int cost;

        public Edge(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }
}