[BOJ] 백준 2213 트리의 독립집합 (Swift)

문제

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

2213번: 트리의 독립집합

풀이

트리에서 DP를 사용하는 문제입니다.
독립 집합을 만들 때, 최대 가중치를 구하기 위해 다음과 같이 작성할 수 있습니다.

1. 현재 노드를 선택헀다면, 다음 노드를 선택 못함 (현재노드의 가중치를 더함)
2. 현재 노드를 선택하지 않았다면, 다음 노드를 선택하거나 안하거나. max(다음 노드를 선택한 값, 다음 노드 선택 안한 값)

점화식은 다음과 같이 세울 수 있습니다.
$f(n, 0) =$: n번 노드를 선택 안함, $f(n, 1) =$: n번 노드를 선택
$f(n, 0) = max(f(next, 0), f(next, 1))$
$f(n, 1) = cost(n) + f(next, 0)

이제 최대 가중치는 구하였고, 이 정점들은 어떻게 구할 수 있을까요?

저는 3차원 배열을 선언하였고, 다음과 같이 사용하였습니다.
$route(n, 0) =$: n번째 노드를 선택안했을 때 최대 값을 가지는 정점들
$route(n, 1) =$: n번째 노드를 선택했을 때 최대 값을 가지는 정점들

트리를 탐색하면서 지나온 정점들을 배열로 넣어주었습니다.

root를 1이라고 가정한 후,
1번 노드를 선택한 경우와, 안한경우를 둘로 나누어서 더 큰 값이 최대 독립집합의 크기가 될 것이고
그때의 정점을 오름차순으로 출력시켜주었습니다.

소스코드

후기

기존에 트리 + DP 문제를 풀어서 최대값을 구하는데는 무리가 없었지만 추적하는 것이 까다로웠습니다.