[BOJ] 17398번 통신망분리

1. 이해하기

• 하나의 통신망을 Q번을 통해서 분리하는데 드는 비용을 구하는 문제이다.
• 통신탑 연결을 끊었는데 통신망이 나눠지지 않는다면 비용은 0이다. 통신망이 나눠진다면 나눠진 통신망이 가지고 있는 통신탑의 갯수를 곱한 값이 비용이다. 예를 들어 통신탑 연결을 끊었는데 3개의 통신탑, 3개의 통신탑 이렇게 두개의 통신망으로 나눠졌다면 3*3=9의 비용이 드는 것이다.
• 유니온 파인드를 이용해서 풀 수 있다.
• 유니온 파인드는 각 정점을 잇는 방법인데, 여기서는 각 정점을 끊는 방법이다.
• 역으로 생각하면 풀 수 있다. 끊는 통신탑에 대해서는 처음에 연결을 하지 않고 한번 더 역으로 방문하면서 이어주는 방법이다.

---

2. 구현하기

package algo;

import java.util.Arrays;
import java.util.Scanner;

public class B17398통신망분할 {
	static int N,M,Q;
	static int[] p;
	static int[][] edge;
	static int[] order;
	static boolean[] check;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		Q = sc.nextInt();
		p = new int[N+1];
		edge = new int[M][2];
		order = new int[Q];
		check = new boolean[M];
		makeSet();
		for(int i = 0; i < M; i++) {
			edge[i][0] = sc.nextInt();
			edge[i][1] = sc.nextInt();
		}
		for(int i = 0; i < Q; i++) {
			order[i] = sc.nextInt()-1;
			check[order[i]] = true;
		}
		
		for(int i = 0; i < M; i++) {
			if(check[i]) continue;
			union(edge[i][0],edge[i][1]);
		}
		
		long ans = 0;
		for(int i = Q-1; i >= 0; i--) {
			int idx = order[i];
			if(find(edge[idx][0]) == find(edge[idx][1])) {
				union(edge[idx][0],edge[idx][1]);
			} else {
				ans += (long)p[find(edge[idx][0])]*(long)p[find(edge[idx][1])];
				union(edge[idx][0],edge[idx][1]);
			}
		}
		System.out.println(ans);
		sc.close();
	}
	
	static void makeSet() {
		Arrays.fill(p, -1);
	}
	
	static int find(int x) {
		if(p[x] < 0) return x;
		return p[x] = find(p[x]);
	}
	
	static void union(int x, int y) {
		int a = find(x);
		int b = find(y);
		if(a==b) return;
		p[a]+=p[b];
		p[b]=a;
	}
}