4 - 3. Xayahh-Rakann at Moloco (Hard)

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

15509번: Xayahh-Rakann at Moloco (Hard)

 
서로소 집합을 만드는 문제입니다.
영문으로 써져있어서 풀기가 너무 귀찮은데, 전 이 정도로 물러날 코더가 아니죠.
 
보시는 분들 중엔 물러나실 분도 계실 수 있어 친절하게 문제 요약을 해드리자면, 다음과 같습니다. 후후
 
어떤 실험에 쓰이는 물질(dark matters)이 있는데, 특정 물질들은 서로 멀리 떨어져있으면 위험합니다.
ㅂㄷㅂㄷ 물질도 붙어댕기는데.. (커플 지옥 솔로 천국)
따라서 일정 거리 유지해야하는 물질들은 문제에 주어지는 조건에 맞춰 묶어두고 (서로소 집합으로) 이 묶은 집합들을 토대로 전체 집합을 조건에 맞는 두개의 쌍으로 나눌 수 있느냐를 물어보는 문제입니다.
 
최종적으로 만들어질 두개의 한 쌍은 물질의 개수가 n개 일때 입력 k가 주어지는데요. 이때 두 그룹 중 하나의 크기는 k가 되어야하고, 나머지 하나의 그룹은 n-k가 되어야합니다.
 
예시 입력을 통해 좀 더 설명을 보충해 보겠습니다.
6 3 4
2 3
3 4
5 6
 
이런 경우엔 집합이 아래와 같이 묶이겠습니다.
[1] [2 3 4] [5 6]
각 집합의 크기는 1, 3, 2 이고 이때 k가 4니까, [1]과 [2 3 4]를 묶고, [5 6]을 두면 문제의 조건에 따라 "SAFE"로 출력할 수 있습니다.
앗! DOOMED 예시는 없냐구요? 넵 >_o
 
풀이 방법

1. 우선 서로소 집합으로 입력으로 주어지는 m개를 묶어줍시다.
2. 묶인 각 집합의 크기를 리스트에 저장합니다. (내림차순 정렬)
3. 가장 큰 집합의 크기부터 가져와서 그 합들을 통해 k를 0으로 만들 수 있는지 확인합니다.

 
이쯤오면 솔직히 서로소 집합은 코파는 것보다 쉬우니.. 더 이상의 설명은 생략합니다.
코파는 것 보다 쉬운건 뇌절아니야? 아뇨. 코파는거 생각보다 쉽지 않습니다.
코 안의 3차원 좌표를 잡고 적당한 힘을 어떤 방향으로 줄지 고려해야하는 벡터의 원리가 숨어있거든요.
진짜 뇌절
 
여기 3번에서 완탐이 사용됩니다.
우리같은 코더들은 주절주절 떠드는것 보다 코드가 편하니 코드로 보겠습니다.

	private static String knapsack(int k) {
		ArrayList<Integer> pair = new ArrayList<>();

		for(int p: parent) {
			if(p >= 0) continue;
			pair.add(-p);
		}

		boolean[] dp = new boolean[SIZE];
		dp[0] = true;

		for (int p: pair) {
			boolean[] sack = new boolean[SIZE];

			for (int size = 0; p + size <= parent.length; size++) {
				if (!dp[size]) continue;
				sack[p + size] = true;
			}

			for (int size = 0; size <= parent.length; size++) {
				dp[size] |= sack[size];
			}
		}

		return dp[k] ? "SAFE": "DOOMED";
	}

 
티스토리 코드 하이라이팅은 간만에 봐도 꼴받네요.
 
그리디는 왜 안될까요?
 

아니시에이팅 대충 정렬해서 구하면 되는거 아니야?

이런 의문을 가지신다면.. 좋긴하겠지만 안가지셔도 됩니다. 명확한 답은 존재하니까요 ^^

정렬하는 경우 어떻게 처리될지 시식만 조금 해보죠.
 

1. k보다 큰 집합의 크기는 신경 쓸 필요 없습니다.
2. k와 같은 크기의 집합이 있다면? 땡큐죠.
   1. 1, 2는 모르시면 초등학교 수학부터 다시하셔야..ㅜㅜ
3. k보다 작은 집합의 크기를 정렬하고 이를 순차적으로 합했을 때 과연 k를 만들 수 있는가?

3번이 문제겠죠. (왜 문젠지 모르셔도 괜찮습니다. 공부하는 상황에선 이제부터라도 알고 신경쓰면 됩니다.)
문제라는 것은 예를 들면 이런 경우겠죠.
집합을 크기 역순으로 정렬했을 때 x1, x2, x3, ... xn이 있고 k를 받았다고 가정해봅시다. (단, k > x1)
이 때, x1 + x2 == k 일 수도 있으나 x3 + x5 + ... + xn == k 일 수도 있잖아요. 이것도 문제는 안되겠지만, 여기까지 와서는 무조건 떠오를 수 밖에없죠.

• 앞의 조건과 동일하게 x3 + x5 + ... + xn == k라고 합시다. 근데 x2가 기존의 x2보다 좀 더 큰 값을 갖고있다고 생각해봅시다.
• 이땐, x1 + x2 > k가 되겠죠.
• 즉, k - x1을 앞에서 먼저 진행해버리면 x2 == (k - x1)이 아니니까, 이전처럼 값을 찾을 수 없게될 수 도 있습니다.
• 그럼 x1 잡고 x2 잡고... xn 잡고 .. 더블루프 트리플루프 .. 트러플수프(냠냠..) 때리냐? 그건 시간이 우릴 허락하지 않습니다.
• 따라서, DP를 적용해서 완탐을 돌리면 간단합니다.

아래와 같은 예시가 적나라하게 정렬을 통해 처리하는그리디한 방식은 허용되지 않음을 보여줍니다.
N = 11, m = 8, k = 6
1 2
2 3
3 4
4 5
6 7
6 8
6 9
11 10
 
욕심을 줄이고, 무소유의 삶을 삽시다.
이젠 뭐 요정도 문제 시간복잡도 계산해드리는건 무례할 정도니 참고 넘어가겠습니다.
해답 코드입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	private static int[] parent;
	private static final int SIZE = 1_001;

	public static void main(String[] args) throws Exception {
		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 k = Integer.parseInt(st.nextToken());

		init(n);

		while(m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;

			merge(a, b);
		}

		System.out.println(knapsack(k));
	}

	private static String knapsack(int k) {
		ArrayList<Integer> pair = new ArrayList<>();

		for(int p: parent) {
			if(p >= 0) continue;
			pair.add(-p);
		}

		boolean[] dp = new boolean[SIZE];
		dp[0] = true;

		for (int p: pair) {
			boolean[] sack = new boolean[SIZE];

			for (int size = 0; p + size <= parent.length; size++) {
				if (!dp[size]) continue;
				sack[p + size] = true;
			}

			for (int size = 0; size <= parent.length; size++) {
				dp[size] |= sack[size];
			}
		}

		return dp[k] ? "SAFE": "DOOMED";
	}

	private static void init(int n) {
		parent = new int[n];
		Arrays.fill(parent, -1);
	}

	private static int find(int x) {
		if (parent[x] < 0) return x;
		return parent[x] = find(parent[x]);
	}

	private static void merge(int x, int y) {
		x = find(x);
		y = find(y);

		if(x == y) return;

		if(parent[x] < parent[y]) {
			parent[x] += parent[y];
			parent[y] = x;
		}
		else {
			parent[y] += parent[x];
			parent[x] = y;
		}
	}
}