[백준]#2406 안정적인 네트워크

문제

한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.

네트워크 시설에서는 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다. 예를 들어 1, 2번 컴퓨터가 직접 연결되어 있고, 1, 3번 컴퓨터가 직접 연결되어 있다면, 이것은 2, 3번 컴퓨터가 연결되어 있는 효과도 발휘한다는 것이다.

회사 측에서는 네트워크에 고장이 발생하더라도 컴퓨터들이 연결되어 있도록 안정적인 네트워크를 구축하고자 한다. 네트워크에 고장이 발생하는 경우는 두 가지가 있다. 첫 번째는 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우이다. 회사 측은 이런 경우에도 이 두 컴퓨터가 다른 컴퓨터들을 경유하여 연결되어 있기를 원한다. 두 번째는 컴퓨터가 고장 나는 경우이다. 회사 측은 이런 경우에는 고장 나지 않은 컴퓨터들끼리 연결되어 있기를 원한다.

예제로 주어진 입력에서 1, 2번 컴퓨터의 연결이 끊어지더라도, 이 두 컴퓨터는 3번 컴퓨터를 통해서 연결되게 된다. 하지만 1번 컴퓨터가 고장 나는 경우에는 5번 컴퓨터가 다른 컴퓨터들과 연결되어 있지 못하게 된다. 따라서 5번 컴퓨터를 다른 컴퓨터와 직접 연결해 주어야 한다.

두 컴퓨터를 연결하는 데 소요되는 비용은 일정하지 않다. 당신은 네트워크의 연결 상태를 입력받아 이 네트워크가 안정적인 네트워크인지 판별하고, 만약 아닐 경우에는 최소 비용으로 회사의 네트워크가 안정적이 되도록 하여야 한다.

입력

첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, x번 컴퓨터와 y번 컴퓨터가 직접 연결되어 있음을 의미한다. 다음 n개의 줄에는 인접 행렬의 형태로 두 컴퓨터를 연결할 때 드는 비용이 주어진다. 이 값은 1 이상 30,000이하의 정수이며, i번 컴퓨터와 j번 컴퓨터를 연결할 때 드는 비용은 j번 컴퓨터와 i번 컴퓨터를 연결할 때 드는 비용과 같다. 본사의 컴퓨터는 항상 1번 컴퓨터이다.

출력

첫째 줄에 최소 비용 X와 연결할 컴퓨터들의 쌍의 개수 K를 출력한다. 다음 K개의 줄에는 두 정수로 연결할 컴퓨터들의 번호를 출력한다. 만약 주어진 입력이 안정적인 네트워크라면 X=0이고 K=0이 된다.

예제 입력 1

5 2
3 2
3 4
0 100 50 100 100
100 0 100 100 100
50 100 0 20 100
100 100 20 0 80
100 100 100 80 0

예제 출력 1

80 1
5 4

풀이

이 문제는 kruskal(크루스칼) 알고리즘을 이용해서 풀 수 있었다. MST(최소 스패닝 트리) 문제였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int edge_cnt = 0;

        parent = new int[n+1];
        for(int i=1; i<=n; i++)
            parent[i] = i;

        for(int i=0; i<m; i++) {
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

            if(find(a)==find(b)) continue;

            edge_cnt++;
            union(a, b);
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        ArrayList<Pair> list = new ArrayList<>();
        int total = 0;

        for(int i=1; i<=n; i++) {
            input = br.readLine().split(" ");
            if(i==1) continue;
            for(int j=i; j<n; j++) {
                pq.add(new Pair(i, j+1, Integer.parseInt(input[j])));
            }
        }

        while(!pq.isEmpty() && edge_cnt<n-2) {
            Pair temp = pq.poll();

            int a = temp.start;
            int b = temp.end;

            if(find(a)==find(b)) continue;

            union(a, b);
            total += temp.cost;
            edge_cnt++;
            list.add(new Pair(temp.start, temp.end, 0));
        }

        System.out.println(total+" "+list.size());

        for(Pair temp : list) {
            System.out.println(temp.start + " " + temp.end);
        }

        pq.clear();
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a<b)
            parent[b] = a;

        else
            parent[a] = b;
    }

    public static int find(int a) {
        if(parent[a]==a)
            return a;

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

    public static class Pair implements Comparable<Pair>{
        int start;
        int end;
        int cost;

        public Pair(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        public int compareTo(Pair p) {
            return this.cost > p.cost ? 1 : -1;
        }
    }
}