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

문제

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

리뷰

골목 대장 호석 시리즈의 첫번째 문제이다. 백트래킹 + 브루트포스 방식으로도 풀이할 수
있다고 하지만, 필자는 이분 탐색 + 다익스트라의 구성으로 풀이했다.

다익스트라 로직내에서는 고정된 특정 비용 x 미만의 간선들만 채택하며 최단 경로 비용을
구한다. 로직의 반환형은 boolean으로 x 미만의 간선들만 채택하여 B까지 C이하의
비용으로 갈 수 있는 경로가 존재하는지 (dist[B]<=C) 여부를 반환한다.

다익스트라 로직을 진행하기 위한 특정 비용 x는 이분 탐색을 통해 결정한다. 비용의
범위가 1~1000이므로 low 를 1, high 를 1001로 설정하여 탐색을 진행하며
다익스트라의 반환값이 참일 때는 high를 낮춰주어 다 낮은 범위에서 탐색하고, 거짓일
때는 범위를 높여준다.

로직의 시간복잡도는 이분탐색이 $O(log1001)=O(k)$의 상수 형태이고
다익스트라가 $O(NlogM)$의 형태를 띄므로 결론적으로 $O(kNlogM)$으로 수렴한다.
따라서 $N=10$, $M=10 \times 9 /2 = 45$ 인 최악의 경우에도 무난히 제한 조건
3초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int N, C;
    static long[] dist;
    static List<List<Node>> graph = new ArrayList<>();
    static long answer = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());
        int A = parseInt(st.nextToken());
        int B = parseInt(st.nextToken());
        C = parseInt(st.nextToken());

        dist = new long[N + 1];
        graph.add(null);
        for (int i = 0; i < N; i++)
            graph.add(new ArrayList<>());

        int u, v;
        long w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = Long.parseLong(st.nextToken());

            graph.get(u).add(new Node(v, w));
            graph.get(v).add(new Node(u, w));
        }

        binSearch(A, B);
        System.out.println(answer);
        br.close();
    }

    static void binSearch(int start, int end) {
        long low = 1;
        long high = 1001;
        long mid;

        while (low <= high) {
            mid = (low + high) / 2;

            if (dijkstra(start, end, mid)) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }

    static boolean dijkstra(int start, int end, long x) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(n -> n.w));
        Arrays.fill(dist, MAX_VALUE);
        dist[start] = 0;
        pq.offer(new Node(start, dist[start]));

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

            if (dist[cur.v] < cur.w) continue;

            for (Node next : graph.get(cur.v)) {
                if (next.w > x) continue;

                if (dist[next.v] > dist[cur.v] + next.w) {
                    dist[next.v] = dist[cur.v] + next.w;
                    pq.offer(new Node(next.v, dist[next.v]));
                }
            }
        }

        return dist[end] <= C;
    }

    static class Node {
        int v;
        long w;

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

결과