[BOJ] 백준 2213. 트리의 독립집합 (Gold I) (+테스트케이스 존재)

나름 유명한 문제인데, 내가 아직 이걸 안풀었다는 사실을 알고 시도해본 문제.

내가 treeDp에 약해서 그런건진 모르겠는데 생각보다 좀 틀렸다. (2회 WA, 3회째 AC)

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

2213번: 트리의 독립집합

tree dp 중에선 꽤나 웰노운이라 해서 포스팅해보려 한다.

---

의식의 흐름 및 해설

트리에서의 노드를 포함하는지의 여부에 따라 최댓값이 달라지는 흔한 treedp 유형이다.

그럼에도 불구하고, 트리dp, dp역추적은 내가 어려워하는 유형이라 꽤나 쫄면서 접근했다.

 

일단, dp테이블은 dp[10001][2] (방문하는지의 여부에 따라 갈리므로 방문여부 상탯값을 추가로 저장해야된다.)로 둔다.

따라서 같은 노드를 2번 이상 방문하기 때문에 아래와 같이 init함수로 단방향 트리로 만들어준다.

void init(int cur) {
	visit[cur] = true;
	for (auto i : v[cur]) {
		if (!visit[i]) {
			c[cur].push_back(i);
			init(i);
		}
	}
}

v는 edge끼리의 노드쌍을 저장한 벡터,

c는 단방향 트리쌍을 저장하는 벡터이다.

 

이제 최댓값을 구해주어야 한다.

현재 노드가 독립집합에 포함된다면, 다음 노드는 독립집합에 포함되지 않아야 하며,

현재 노드가 독립집합에 포함되지 않는다면, 다음 노드는 독립집합에 포함될 수도, 포함되지 않을 수도 있다.

현재 노드가 포함되지 않는다고, 다음 노드가 포함되는 경우가 반드시 최대가 아닌 경우가 존재하기 때문이다. 예를 들어, 인접한 양옆 노드가 굉장히 작은 값이고, 그 옆 노드가 굉장히 큰 경우일 경우가 그런 경우이다. 이는 쉽게 떠올릴 수 있다.

 

따라서 코드는 아래와 같이 짜도록 한다.

for (auto i : c[cur]) {
	int tmp = dp(i, 0);
	if (!flag)
		tmp = max(tmp, dp(i, 1));
	ret += tmp;
}
if (flag)
	ret += a[cur];
return ret;

솔직히 여기까진 무난하다.

이 문제의 핵심은 역추적이다.

 

이 문제는 트리이기 때문에, 역추적은 dfs로 실행하면 되며,

난 dfs 시작점을 dp를 처음 돌린 1번 노드로 잡았다.

 

역추적으로는, dp테이블에 저장된 값에서 현재 노드를 독립집합에 포함시킨 경우가 포함시키지 않는 경우보다 클 경우, 그리고 이전노드가 독립집합에 포함되지 않았을 경우를 따지면 된다.

void trace(int cur, int prev = -1) {
	if (d[cur][1] > d[cur][0] && !visit[prev]) {
		res.push_back(cur);
		visit[cur] = true;
	}
	for (auto i : c[cur]) {
		if (i != prev)
			trace(i, cur);
	}
}

---

시행착오

처음에는 정렬을 하지 않아서 바로 WA(틀렸습니다)를 받았다.

그런데, 정렬을 해도 9%에서 WA를 받아 좀 더 생각을 해보니 아래와 같은 반례에서 잘못된 값을 출력하고 있었다.

8
20 30 20 40 100 100 60 30
1 2
1 5
2 3
2 4
2 6
6 7
6 8
ans: 
260
3 4 5 6

인접노드끼리 출력해주는 것을 허용해버리면 위 데이터에서 3 4 5 6 7 8을 출력할 것이다.

인접노드 출력을 막아주니 AC를 받았다.

---

코드

// 211003 #2213 트리의 독립집합 Gold I
// treeDP
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 10011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
int N, a[MAX], d[MAX][2];
vector<int> v[MAX], c[MAX], res;
bool visit[MAX];
void init(int cur) {
	visit[cur] = true;
	for (auto i : v[cur]) {
		if (!visit[i]) {
			c[cur].push_back(i);
			init(i);
		}
	}
}
int dp(int cur, int flag) {
	int& ret = d[cur][flag];
	if (ret != -1)
		return ret;
	ret = 0;
	for (auto i : c[cur]) {
		int tmp = dp(i, 0);
		if (!flag)
			tmp = max(tmp, dp(i, 1));
		ret += tmp;
	}
	if (flag)
		ret += a[cur];
	return ret;
}
void trace(int cur, int prev = -1) {
	if (d[cur][1] > d[cur][0] && !visit[prev]) {
		res.push_back(cur);
		visit[cur] = true;
	}
	for (auto i : c[cur]) {
		if (i != prev)
			trace(i, cur);
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < N - 1; i++) {
		int n1, n2;
		cin >> n1 >> n2;
		v[n1].push_back(n2);
		v[n2].push_back(n1);
	}
	init(1);
	memset(d, -1, sizeof(d));
	int ans = max(dp(1, 0), dp(1, 1));
	cout << ans << "\n";
	fill(visit, visit + MAX, false);
	trace(1);
	sort(all(res));
	for (auto i : res)
		cout << i << " ";
}

상태값을 dp테이블에 포함시켰으므로,

dp(1, 0)을 한 후에, dp(1,1)을 돌릴 때 memset(초기화)를 할 필요가 없다.

---

꽤나 재밌는 문제인데, 아무리 생각해도 아래 문제의 판박이다.

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

1949번: 우수 마을

그래도 한번 위 문제를 참고하지 않고 스스로 풀어보면서 감을 찾는 시간을 가져보았다.

잘 해결한듯?