백준 2213번: 트리의 독립집합 (Python)

접근

dp[i][0] 을 i를 포함한 부분 집합 가중치의 최대값, 그리고 dp[i][1] 을 i를 포함하지 않은 부분 집합 가중치의 최대값으로 지정하고 dfs로 탐색하면서 dp 값을 갱신해줌으로써 문제를 해결해 줄 수 있다.

예를 들어 a 노드의 자식노드 b, c 노드가 있을 때, a 노드를 포함하는 부분 집합 가중치의 최대값 dp[a][0] 에는 b 노드를 포함하지 않는 부분 집합 가중치의 최대값 dp[b][1] 과 c노드를 포함하지 않는 부분집합 가중치의 최대값 dp[c][1] 을 더해줄 수 있다. 독립 집합 S 에 a 를 포함할 경우 그와 인접하는 b, c 는 독립 집합 S 에 포함될 수 없기 때문이다. 임의의 노드 1에서 부터 시작하여 dfs 알고리즘을 이용하여 제일 깊은 곳부터 dp를 채워나가가면서 갱신해줌으로써 최종적으로 dp[1][0] 에는 1을 포함한 독립 집합의 가중치, dp[1][1] 에는 1을 포함하지 않는 독립 집합의 가중치가 저장되게 되는데 이 두 값 중 큰 값을 출력해주면 된다.

코드

import sys

n = int(sys.stdin.readline())
weight = [0] + list(map(int, sys.stdin.readline().split()))
lines = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    lines[a].append(b)
    lines[b].append(a)
visited = [0] * (n + 1)
dp = [[0, 0] for _ in range(n + 1)]
num = [[[], []] for _ in range(n + 1)]


def dfs(start):
    visited[start] = 1
    dp[start][0] = weight[start]
    num[start][0].append(start)
    for i in lines[start]:
        if not visited[i]:
            dfs(i)
            dp[start][0] += dp[i][1]
            for j in num[i][1]:
                num[start][0].append(j)
            if dp[i][0] <= dp[i][1]:
                dp[start][1] += dp[i][1]
                for j in num[i][1]:
                    num[start][1].append(j)
            else:
                dp[start][1] += dp[i][0]
                for j in num[i][0]:
                    num[start][1].append(j)


dfs(1)
if dp[1][0] >= dp[1][1]:
    i = 0
else:
    i = 1
print(dp[1][i])
tmp = num[1][i]
tmp.sort()
print(*tmp)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!