[백준] 통신망 분할 (17398, Java)

문제

BOJ의 인기스타, 방송인 권욱제는 통신 회사에 취업했다. 현재 이 통신 회사는 너무나 큰 통신망을 한 지사에서 관리하느라 큰 비용을 지불하고 있었다. 그래서 회사는 최근 IT의 트렌드 중 하나인 '탈중앙화'에 편승하여, 통신망을 분할하도록 결정했다. 그래서 욱제한테 통신망을 분할 할때 발생하는 비용을 분석하도록 지시했다.

현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠진 두 개의 통신망에 속한 통신탑들의 갯수의 곱이 되며, 나누어지지 않을 경우 0이다.

<그림 1>

그림 1을 예시로 할때, 연결 (3, 4)를 제거하면 {1, 2, 3}, {4, 5, 6}으로 분할 되며, 이때 발생하는 비용은 3 × 3 = 9가 된다. 대신 연결 (2, 3)을 제거하면, 망이 나눠지지 않았기에 비용은 0이 된다.

욱제는 회사의 요청에 따라 Q번의 제거를 통해 나오는 비용의 합을 구해야 한다. 하지만 욱제는 회사의 통신망을 이용해 방송하기 바쁘기 때문에 우리가 도와주자.

입력

첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q ≤ M)

두 번째 줄부터 M개의 줄에 걸쳐 두 개의 자연수 X, Y가 공백으로 구분되어 주어진다. 이는 X 통신탑과 Y 통신탑 사이에 연결이 있음을 뜻한다. (1 ≤ X, Y ≤ N, X ≠ Y)

중복된 연결은 주어지지 않으며, 모든 통신탑은 처음엔 하나의 통신망에 속한다. 조건에 의해 자기 자신과 연결이 있는 통신탑은 없다.

그 다음 줄부터 Q개의 줄에 걸쳐 제거될 연결의 번호인 자연수 A가 주어진다. 이는 A번째로 입력된 (X, Y)의 연결이 제거되었음을 의미한다. (1 ≤ A ≤ M)

이미 제거된 연결은 다시 제거되지 않으며, 제거는 입력 순서대로 진행된다.

출력

첫 번째 줄에 Q개의 연결을 순서대로 제거하는데 드는 비용의 합을 출력한다.

예제 입력 1 복사

4 4 3
1 2
2 3
3 4
1 4
4
2
3

예제 출력 1 복사

5

첫 번째로 제거되는 연결은 (1, 4)로, 통신망 {1, 2, 3, 4}가 분리되지 않아 비용이 0이다.

두 번째로 제거되는 연결은 (2, 3)으로, 통신망 {1, 2, 3, 4}가 {1, 2}와 {3, 4}로 분리되어 비용이 2 × 2 = 4이다.

세 번째로 제거되는 연결은 (3, 4)로, 통신망 {3, 4}가 {3}과 {4}로 분리되어 비용이 1 × 1 = 1이다.

결과적으로 총 비용은 0 + 4 + 1 = 5이다.

 

• 이 문제는 간선을 분리할 때 각기 다른 두 개의 조각으로 나누어질 경우 각 조각의 크기를 곱한 뒤 결과에 더해주는 문제이다.
• 이 때, 유니온-파인드를 생각해 줄 수 있는데 위의 문제 그대로 분리시키는 것이 아니라 반대로 생각해서 합칠 때의 각 크기를 구해주는 방식을 사용하였다.
• 위의 예제를 봤을 때, 1, 2, 3, 4의 인덱스를 가지는 간선 집합이 존재하는데, 그 중 분리시켜야 하는 것은 순서대로 4, 2, 3 인덱스의 간선이다. 그렇다면 1번 간선은 연결시켜놓고, 초기 size 배열은 1번과 2번 중 더 작은 값이 1번을 기준으로 size[1] = size[1] + size[2] 가 된다. (size 배열은 각 조각의 크기를 보다 구하기 쉽게 하기 위한 배열)
• 반대 순서대로 3번 인덱스부터 차례대로 합치면서 만일 union 메서드의 리턴값이 false인 경우는 이미 하나의 조각인 경우이기 때문에 고려하지 않고 true인 경우 양쪽 조각의 곱(find 메서드로 부모 인덱스를 구한 후 size[부모 인덱스]로 조각의 크기를 구할 수 있다.)을 구해준다.
• 이 때, 주의해야 할 점은 각 size의 합이 최대인 경우가 100000이고, 이를 나누어서 곱해주었을 때 최댓값은 25억이므로 int 범위를 넘어간다. 따라서, long으로 처리해주어야 한다.

import java.util.*;
import java.io.*;

public class Main {

    static int N, M, Q;
    static int[][] arr;
    static Stack<Integer> myQ = new Stack<>();
    static int[] uf, size;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        Q = stoi(st.nextToken());
        arr = new int[M+1][2];
        for (int i = 1; i <= M; ++i) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = stoi(st.nextToken());
            arr[i][1] = stoi(st.nextToken());
        }

        boolean[] connected = new boolean[M+1];
        Arrays.fill(connected, true);
        for (int i = 0; i < Q; ++i) {
            int a = stoi(br.readLine());
            myQ.push(a);
            connected[a] = false;
        }

        uf = new int[N+1];
        size = new int[N+1];
        for (int i = 1; i <= N; ++i) {
            uf[i] = i;
            size[i] = 1;
        }

        for (int i = 1; i <= M; ++i) {
            if (connected[i]) {
                int a = find(arr[i][0]), b = find(arr[i][1]);
                if (union(arr[i][0], arr[i][1])) {
                    if (a < b) {
                        size[a] += size[b];
                    } else {
                        size[b] += size[a];
                    }
                }
            }
        }

        long ans = 0;
        while (!myQ.isEmpty()) {
            Integer now = myQ.pop();
            int a = find(arr[now][0]), b = find(arr[now][1]);
            if (union(arr[now][0], arr[now][1])) {
                ans += (long)size[a] * size[b];
                if (a < b) {
                    size[a] += size[b];
                } else {
                    size[b] += size[a];
                }
            }
        }
        System.out.println(ans);
        br.close();
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (x > y) {
            uf[x] = y;
        } else {
            uf[y] = x;
        }
        return true;
    }

    static int find(int x) {
        if (uf[x] == x) return x;
        return uf[x] = find(uf[x]);
    }

    static int stoi(String input) {
        return Integer.parseInt(input);
    }


}