[백준 17398]https://www.acmicpc.net/problem/17398
문제 조건
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)
이미 제거된 연결은 다시 제거되지 않으며, 제거는 입력 순서대로 진행된다.
문제 풀기 전 설계
그래프에서 몇 개의 노드를 그룹화 하는 방법 -> 분리 집합
하지만 Union-Find 기법은 병합은 되지만 분리는 하지 못한다.
그 문제를 어떤 방법으로 해결할 수 있을까?
문제 코드
package Baekjoon.dataStructure.disjointSet;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
public class BOJ_17398 {
static int[] parent;
static long[] groupSize;
static Connection[] connects;
static class Connection {
int a, b;
public Connection(int a, int b) {
this.a = a;
this.b = b;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
parent = new int[N + 1];
for (int i = 1; i <= N; i++) parent[i] = i;
groupSize = new long[N + 1];
Arrays.fill(groupSize, 1);
connects = new Connection[M + 1];
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
connects[i] = new Connection(a, b);
}
/**
* 제거 예정인 간선을 저장해 두고 나머지 간선을 모두 연결한 상태로
* 제거 역순으로 그래프를 Union 작업하여 문제를 해결한다.
* Union-Find 기법은 그래프를 분리하는 상황에서 쓰지 못하기 때문에
* 문제를 거꾸로 생각해 해결한다.
*/
boolean[] cutLine = new boolean[M + 1];
Stack<Integer> stack = new Stack<>();
while (Q-- > 0) {
int idx = Integer.parseInt(br.readLine());
cutLine[idx] = true;
stack.push(idx);
}
for (int i = 1; i <= M; i++) {
if (cutLine[i]) continue;
int a = connects[i].a;
int b = connects[i].b;
union(a, b);
}
long ans = 0L;
while (!stack.isEmpty()) {
Connection now = connects[stack.pop()];
int a = find(now.a);
int b = find(now.b);
// 서로 다른 그룹이라면 제거 비용을 구하여 합함.
if (a != b) ans += groupSize[a] * groupSize[b];
union(a, b);
}
System.out.println(ans);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (a > b) {
int temp = a;
a = b;
b = temp;
}
if (a != b) {
groupSize[a] += groupSize[b];
parent[b] = a;
}
}
private static int find(int x) {
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
}
문제 풀이
Union-Find는 병합만 가능하다.
그렇기에 간선 정보를 미리 저장해 놓은 후 제거 예정이 없는 간선을 모두 Union 연산으로 연결한다.
그 후 제거 역순으로 간선 하나씩 Union 연산하여 통신망 크기를 구하고, 그 값을 이용해 제거 비용을 계산해 합한다.
Review
Union-Find 기법을 응용하여 풀어야 했기 때문에 어려웠다. 간선의 "제거" 라는 키워드를 "병합" 으로 생각하는 사고의 전환을 요하는 문제라 처음 풀이법을 보았을 때 놀라웠다. 문제를 다양한 관점으로 생각하는 능력을 기르고 싶다.
