백준 20303 - 할로윈의 양아치

이번 문제는 백준의 골드 3, 할로윈의 양아치 문제이다.
문제를 한 번 차근차근 읽어보도록 하자.

최대 30000명의 아이와 100000개의 관계가 주어진다.
이 때, K명 이상의 아이의 사탕을 뺏으면 어른들이 알게 된다.
어른들이 모르게 최대 몇 개의 사탕을 뺏을 수 있을까?

그룹화

가장 먼저 든 생각은 아이들을 그룹화 해야겠다는 생각이다.
어떤 아이의 사탕을 뺏았을 때, 관계가 있는 모든 아이의 사탕을 뺏는다.
그럼 해당 아이들은 모두 같은 그룹으로 보면 될 것이다!

이 부분은 유니온 파인드를 이용해서 구현하면 좋겠다고 생각했다.
유니온 파인드는 분리 집합 알고리즘이라고도 불린다.
지금 우리는 서로 분리된 집합을 만드려는 것이니, 적합할 것 같다!
해당 부분은 아래와 같이 구현했다.

init_groups();
for (int i = 1; i <= num; i++)
	cin >> groups[i].second;
// 그룹화를 하기 위해 초기화

for (int i = 0; i < edges; i++) {
	cin >> from >> to;
	if(!check_cycle(from, to))
		do_union(from, to);
}

for (int i = 1; i <= num; i++) {
	int target = groups[i].first;
	int target_candy = groups[i].second;

	if (target == i) // root인 경우 배열에 저장
		group_store.push_back({ target, target_candy });
}

유니온 파인드를 통해서 분리 집합을 구성해주고,
각 집합의 사탕 수와 대표를 vector를 이용해 저장해준다.
map은 중복 검사에 사용되며, 각 집합의 인원 수를 저장하기도 한다.
이렇게 되면 이제 모든 집합의 정보가 저장이 되었다.
이제 관건은 이 정보를 통해 어떻게 최대값을 찾을 수 있는가이다.

완전탐색?

모든 집합을 고르는 경우를 다 생각해보고 그 중에 최대를 고를 수 있을까?
완전 탐색으로 진행했을 때 시간 초과가 발생하지 않을까?

탐색 시간이 최악이 되는 경우는 모든 학생이 분리되어 있을 때일 것이다.
30000명의 학생이 모두 분리된다면 모두 탐색하는 데에 얼마나 걸릴까?
30000명을 중복 없이 모두 고르는 경우의 수는 굉장히 많을 것이다.

만약 최소 값을 구하는 것이었다면, 중지 조건에 의해 시간 단축이 되겠지만
최대 값을 구하는 완전 탐색이기 때문에 시간 초과를 피할 수 없을 것 같다.

Greedy?

그리디하게 문제를 풀 수는 없을까?
간단하게 생각해서, 인원 수가 작은 집합부터 오름차순으로 정렬을 해보자.
이제 앞에서부터 차례대로 선택을 했을 때가 최대가 될까?

만약 10명 이하의 아이만 건드릴 수 있다고 생각해보자.
1(1) 6(4) 7(5) 40(6)와 같이 사탕 수, 인원 수가 정해져있다.
그럼 우리는 그리디하게 선택을 하니 최대가 14개라고 판단할 것이다.
하지만 사실 정답은 1 + 40을 할 수 있는 경우가 된다.

이런 예외 케이스에 의해 이 문제는 그리디하게 풀 수 없다.

DP?

그럼 또 다른 최대, 최소를 구할 수 있는 방식인 동적 계획법은 어떨까?
문제를 계속 읽어 보았을 때, 배낭 문제와 유사하다는 느낌이 들었다.
무게의 제한은 인원 제한으로 치환이 되고, 사탕은 물건의 가치로 치환이 된다.

배낭 문제는 O(N^2)으로 이중 for문으로 풀어낼 수 있는 문제이다.
즉, O(30000^2)가 자명하게 최악의 경우이므로 90,000,000이 된다.
이는 시간 초과에 걸리지 않고 문제를 풀기에 충분하다!
배낭 문제를 복기하며 문제를 한 번 풀어보도록 하자.

0/1 배낭 문제(Knapsack)

0/1 배낭 문제는 물건을 쪼갤 수 없는 배낭 문제를 말한다.
동적 계획법의 대표 문제 중 하나로 꼽힌다.
하지만 매번 풀 때마다 까먹어서 다시보게 되는 것 같다.

보통은 무게를 행, 가치를 열로 두어 O(N^2)에 해결한다.
하지만 이번에 무게 행 한 줄로도 해결 가능함을 알게 되었다.

O(N^2)으로 푸는 원리는 간단하게 아래와 같이 정리한다.

  1. 현재 아이템에서 무게를 늘려가며 가치를 저장한다.
    • 저장되는 가치는 이전 아이템에서 저장되었던 최대 가치이다.
  2. 이전 아이템에 대해 현재 아이템을 가방에 넣을 수 있다면?
    • 이전 아이템에서 저장해온 최대 가치와 현재 아이템의 가치
    • 현재 아이템을 더하지 않은 이전 아이템의 최대 가치
    • 둘 중 큰 값을 저장하도록 한다.
  3. 무게가 꽉 차 가방에 담을 수 없다면?
    • 이전 아이템의 최대 가치를 그대로 저장한다.

그럼 우리는 무게 * 가치의 2차원 공간을 사용한 것이다.
어떻게 무게 행 한 줄로 문제를 해결할 수 있을까?

사실은 굉장히 간단하다.
어차피 우리는 이전 행을 이전 아이템까지의 무게를 저장하는 데에 사용했다.
이 과정을 한 줄에서 그냥 진행해도 상관없지 않을까?

제한 무게부터 현재 아이템의 무게까지 거꾸로 탐색한다.
현재 무게와 이전 아이템 + 현재 무게의 가치를 비교하며 저장한다.
즉, dp[i] = max(dp[i], dp[i - weight[i]] + value[i])를 점화식으로 갖게 된다.

최종적으로 아래와 같이 구현되었다.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
#define pii pair<int, int>

vector<pii> group_store;
pii groups[30001];
int dp[30001][3001], popularity[30001];
int num = 0, edges = 0, limit = 0, from = 0, to = 0;
void optimize() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
}

void init_groups() {
	for (int i = 1; i <= num; i++) {
		groups[i].first = i;
		popularity[i] = 1;
	}
}

int find_parent(int node) {
	if (node == groups[node].first)
		return groups[node].first;

	return groups[node].first = find_parent(groups[node].first);
}

void do_union(int node_x, int node_y) {
	node_x = find_parent(node_x);
	node_y = find_parent(node_y);

	if (node_x < node_y) {
		groups[node_y].first = node_x;
		groups[node_x].second += groups[node_y].second;
		// 사탕 수를 더해서 저장해준다.
		popularity[node_x] += popularity[node_y];
	}
	else {
		groups[node_x].first = node_y;
		groups[node_y].second += groups[node_x].second;
		popularity[node_y] += popularity[node_x];
	}
}

bool check_cycle(int node_x, int node_y) {
	node_x = find_parent(node_x);
	node_y = find_parent(node_y);

	if (node_x == node_y)
		return true;
	return false;
}

int main() {
	optimize();
	cin >> num >> edges >> limit;

	init_groups();
	for (int i = 1; i <= num; i++)
		cin >> groups[i].second;
	// 그룹화를 하기 위해 초기화

	for (int i = 0; i < edges; i++) {
		cin >> from >> to;
		if(!check_cycle(from, to))
			do_union(from, to);
	}

	for (int i = 1; i <= num; i++) {
		int target = groups[i].first;
		int target_candy = groups[i].second;

		if (target == i) // root인 경우 배열에 저장
			group_store.push_back({ target, target_candy });
	}

	for (int i = 0; i < group_store.size(); i++) {
		int curr_kids = popularity[group_store[i].first];
		int curr_value = group_store[i].second;

		for (int j = limit - 1; j >= curr_kids; j--)
			if (j - curr_kids >= 0)
				dp[j] = max(dp[j], dp[j - curr_kids] + curr_value);
	}

	cout << dp[group_store.size()][limit - 1];
	return 0;
}