백준 13911 - 집 구하기

문제

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

풀이

그래프를 변형하고 다익스트라를 적용하여 풀 수 있는 문제였다.

단순히 접근하여, 모든 집 정점에서 다익스트라를 돌리고 맥도날드/스타벅스 정점까지의
거리 합을 계산하는 식으로 구현하면 시간복잡도가 $O(V^2logE)$이 된다. $V$가 최악의
경우 $10,000$이므로 이 방법으론 시간 제한을 통과하지 못한다.

따라서 주어진 그래프를 있는 그대로 활용하지 말고 변형해야 한다. 모든 스타벅스 정점과
거리가 0인 간선으로 연결된 가상의 스타벅스 정점 하나, 모든 맥도날드 정점과 거리가 0인
간선으로 연결된 가상의 맥도날드 정점 하나를 추가로 설정해준다. 이후, 가상의 정점들을
시작점으로 다익스트라를 돌려 최단 거리 배열(dist)을 구성하면 그 정보로 집 정점중
조건을 만족하는 정점을 구할 수 있다. 유의할 점은 추가한 가상의 정점들은 다익스트라로
경로 계산시 거쳐갈 수 없기 때문에, 로직 내에서 무시하도록 구현해야 한다.

로직의 시간복잡도는 다익스트라의 $O(ElogV)$로 수렴하므로 $V=10,000$,
$E=300,000$인 최악의 경우에도 제한 조건 1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.lang.Integer.parseInt;

public class Main {
    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 V = parseInt(st.nextToken());
        int E = parseInt(st.nextToken());

        graph.add(Collections.emptyList());
        IntStream.range(0, V).forEach(i -> graph.add(new ArrayList<>()));

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

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

        st = new StringTokenizer(br.readLine());
        st.nextToken();
        int x = parseInt(st.nextToken());
        Set<Integer> macdonalds = Arrays.stream(br.readLine().split(" ")).map(Integer::parseInt)
                .collect(Collectors.toSet());

        graph.add(new ArrayList<>());
        macdonalds.add(V + 1);
        for (int node : macdonalds) {
            graph.get(node).add(new Node(V + 1, 0));
            graph.get(V + 1).add(new Node(node, 0));
        }

        st = new StringTokenizer(br.readLine());
        st.nextToken();
        int y = parseInt(st.nextToken());
        Set<Integer> starbucks = Arrays.stream(br.readLine().split(" ")).map(Integer::parseInt)
                .collect(Collectors.toSet());

        graph.add(new ArrayList<>());
        starbucks.add(V + 2);
        for (int node : starbucks) {
            graph.get(node).add(new Node(V + 2, 0));
            graph.get(V + 2).add(new Node(node, 0));
        }

        long[] dist1 = dijkstra(V + 1, V + 2);
        long[] dist2 = dijkstra(V + 2, V + 1);

        long answer = Long.MAX_VALUE;
        for (int i = 0; i < dist1.length; i++) {
            if (dist1[i] == Long.MAX_VALUE || dist2[i] == Long.MAX_VALUE) continue;

            if (macdonalds.contains(i) || starbucks.contains(i)) continue;

            if (dist1[i] > x || dist2[i] > y) continue;

            answer = Math.min(answer, dist1[i] + dist2[i]);
        }

        System.out.println(answer == Long.MAX_VALUE ? -1 : answer);
        br.close();
    }

    static long[] dijkstra(int from, int skip) {
        long[] dist = new long[graph.size()];
        Arrays.fill(dist, Long.MAX_VALUE);

        dist[from] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(n -> n.w));
        pq.add(new Node(from, 0));

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

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

            for (Node next : graph.get(cur.v)) {
                if (next.v == skip) continue;

                if (dist[cur.v] + next.w >= dist[next.v]) continue;

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

        return dist;
    }

    static class Node {
        int v;
        long w;

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

결과