백준 2406 - 안정적인 네트워크

문제

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

리뷰

크루스칼을 통해 풀이할 수 있는 문제였다.

문제의 조건을 유심히 봐야하는데 네트워크에 고장이 나더라도 컴퓨터끼리
연결이 되어있도록 만드는 것이 최종 목표이다. 따라서, 모든 컴퓨터들은 기본적으로
본사 컴퓨터인 1과 연결되어 있는 것을 가정하게 된다.

그렇다면 1을 제외한 나머지 컴퓨터간의 연결에서 사라지는 부분이 발생하더라도
모든 컴퓨터가 직/간접적으로 연결될 수 있게 MST를 구성해야 한다는 아이디어를
도출할 수 있다.

아이디어를 구현하기 위해, 기존에 지사 컴퓨터끼리 연결되어 있는 m개의 관계의
경우 크루스칼시 사용할 비용 기준 최소힙에 비용을 0으로 설정하여 저장했다.
(비용의 범위가 1~30,000까지기 때문에 문제가 되지 않는다)
이후, 인접 행렬 형태로 주어지는 연결 비용 정보를 같은 힙에 저장하였다.
한편, 1을 제외한 나머지 컴퓨터들간의 MST를 형성할 것이기 때문에 1과
관련된 간선 정보는 저장하지 않았다.

크루스칼 로직에서는 간선을 채택하며 답 출력을 위한 answer 리스트에 간선을
저장하는데, 이 때 비용이 0인(즉, 새로 연결한 것이 아닌) 간선의 경우 answer에
저장되지 않도록 처리했다.
이를 통해 answer의 size()가 0일 때, 기존의 연결 관계만으로 이미
모든 컴퓨터들이 연결될 수 있는 경우를 처리할 수 있다.

로직의 시간복잡도는 크루스칼의 $O(nlogm)$으로 수렴하고, 이는 $n=1,000$,
$m=10,000$인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

코드

import static java.lang.Integer.parseInt;

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

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));
    static PriorityQueue<Edge> answer = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));

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

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

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

            pq.offer(new Edge(u, v, 0));
        }

        for (u = 1; u <= n; u++) {
            st = new StringTokenizer(br.readLine());
            for (v = 1; v <= n; v++) {
                int w = parseInt(st.nextToken());

                if (u == 1 || v == 1 || u == v) {
                    continue;
                }

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

        long sum = kruskal(n);
        if (answer.size() == 0) {
            System.out.println(0 + " " + 0);
        } else {
            System.out.println(sum + " " + answer.size());
            for (Edge e : answer) {
                System.out.println(e.u + " " + e.v);
            }
        }

        br.close();
    }

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

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

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) {
            return false;
        }

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static long kruskal(int n) {
        int selected = 0;
        long sum = 0;

        while (!pq.isEmpty() && selected < n - 2) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) {
                continue;
            }

            sum += e.w;

            if (e.w == 0) {
                continue;
            }
            answer.add(e);
        }

        return sum;
    }

    static class Edge {
        int u, v, w;

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

결과