백준 20182 - 골목 대장 호석 - 효율성 1

문제

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

리뷰

다익스트라를 응용하여 풀이할 수 있는 문제였다.

골목 대장 호석 시리즈의 첫 문제인 골목 대장 호석 - 기능성의 경우와 마찬가지로
이분 탐색과 다익스트라의 조합으로 접근하였으나 시간 초과가 발생하였다.

사실 다익스트라 로직내에서 비용 기준 최소힙을 이용하여 간선을 탐색하며 최단 경로를
도출하고 있고, 특정 정점에 도달한 순간 최단 경로를 구한 것으로 볼 수 있다.

따라서 다익스트라 로직내에서 도착점에 도달한 순간(cur.v==end) 해당 경우의 비용이
$C$이하인지 (dist[end]<=C) 여부를 바로 반환토록 하여 수행 시간을 개선하였다.

로직의 시간복잡도는 이분탐색의 경우 $log21=k$로 상수 시간에 가깝고 다익스트라가
$O(MlogN)$의 복잡도는 띄므로, $M=500,000$, $N=100,000$인 최악의 경우에도
무난히 제한 조건 3초를 통과한다.

코드

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

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int[] dist;
    static List<List<Node>> graph = new ArrayList<>();

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

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

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

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

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


    static int binSearch(int start, int end, int C) {
        int low = 1;
        int high = 21;
        int mid;
        int answer = -1;

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

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

        return answer;
    }


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

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

            if (cur.v == end) return dist[cur.v] <= C;

            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) continue;

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

        return false;
    }

    static class Node {
        int v, w;

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

결과