백준 30797 - 가희와 여행가요

문제

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

풀이

• 최소 비용으로 도시들을 연결한다는 조건에서 MST로 풀이할 수 있다는 단서를 얻을 수 있음
• 부가적으로 '빠르게 연합'하고자 한다는 조건에서 주어지는 노선(간선)의 시간까지 고려해야 함
• 유니온 파인드를 이용한 크루스칼 알고리즘을 이용해 풀이
  • 연결하는 두 정점 번호, 연결 비용, 연결되는 시간을 저장하는 Edge 클래스 정의
  • 해당 클래스를 통해 간선 정보를 입력받으며 비용 오름차순, 시간 오름차순 우선순위큐에 저장
  • 이후, 우선순위큐에서 간선을 하나씩 꺼내며 유니온 파인드 연산을 통해 n-1개 간선 채택
    • 간선 채택시 비용 합하며 누적, 최종 연결 시간 갱신
  • 앞선 작업 수행 도중 큐가 비면 중단, 이는 모든 정점을 연결할 수 없음을 의미
• 로직의 시간 복잡도는 크루스칼의 $O(ElogE)$로 수렴, 문제의 조건에서 간선의 개수는 최대 $Q=E=2\times 10^5$이므로 제한 시간 1.5초 무난히 통과

코드

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int[] parent;

    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 Q = parseInt(st.nextToken());

        parent = new int[n + 1];
        Arrays.fill(parent, -1);

        PriorityQueue<Edge> pq = new PriorityQueue<>((p1, p2) -> {
            if (p1.w == p2.w) {

                return Integer.compare(p1.t, p2.t);
            }

            return Integer.compare(p1.w, p2.w);
        });
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());
            int t = parseInt(st.nextToken());

            pq.add(new Edge(u, v, w, t));
        }

        int count = 0;
        long sum = 0;
        int endTime = -1;

        while (count < n - 1 && !pq.isEmpty()) {
            Edge e = pq.poll();
            int p1 = find(e.u);
            int p2 = find(e.v);

            if (p1 == p2) {
                continue;
            }

            if (parent[p1] < parent[p2]) {
                parent[p1] += parent[p2];
                parent[p2] = p1;
            } else {
                parent[p2] += parent[p1];
                parent[p1] = p2;
            }

            count++;
            sum += e.w;
            endTime = Math.max(endTime, e.t);
        }

        String answer = endTime + " " + sum;
        System.out.println(count != n - 1 ? -1 : answer);
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) {
            return u;
        }

        return parent[u] = find(parent[u]);
    }

    static class Edge {

        int u, v, w, t;

        public Edge(int u, int v, int w, int t) {
            this.u = u;
            this.v = v;
            this.w = w;
            this.t = t;
        }
    }
}

결과