[BOJ 15509 // C++] Xayahh-Rakann at Moloco (Hard)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15509번 문제인 Xayahh-Rakann at Moloco (Hard)이다.
문제는 아래 링크를 확인하자.

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

15509번: Xayahh-Rakann at Moloco (Hard)

각 jar를 노드로 보고, 서로 떨어지지 않는 관계를 에지로 하는 그래프를 생각해 각 connected component의 크기들을 구하자. 이는 bfs, dfs등을 이용해 쉽게 구할 수 있다. 글쓴이는 disjoint set을 이용해 구현했다.

 

각 connected component들의 크기를 이용해 knapsack DP를 진행하면 나눠놓을 수 있는 jar의 개수들을 구할 수 있다. 이를 이용해 문제를 해결하자. 

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int visited[1001];
int uf[1001], cnt[1001];
int findf(int cur) {
	if (cur == uf[cur]) return cur;
	return uf[cur] = findf(uf[cur]);
}

vector<int> vec;
int dp[2001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, K; cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) uf[i] = i;
	for (int i = 1; i <= N; i++) cnt[i] = 1;

	while (M--) {
		int x, y; cin >> x >> y;
		x = findf(x), y = findf(y);
		if (x == y) continue;
		uf[y] = x;
		cnt[x] += cnt[y];
	}

	for (int i = 1; i <= N; i++) {
		int ii = findf(i);
		if (visited[ii]) continue;
		visited[ii] = 1;
		vec.emplace_back(cnt[ii]);
	}

	dp[0] = 1;
	for (auto& x : vec) {
		for (int i = N; i > -1; i--) {
			if (dp[i]) dp[i + x] = 1;
		}
	}

	if (dp[K]) cout << "SAFE";
	else cout << "DOOMED";
}