BaekJoon 2213번 : 트리의 독립집합 (python)

📝 BaekJoon 2213번 : 트리의 독립집합 (G1 48.748%)

---

🔎 트리의 독립집합 문제

---

📌 아이디어

DFS를 이용한 트리의 탐색과 독립 집합을 분리한 가중치 및 역추적 DP 업데이트를 하는 문제이다.
너무 어렵다.ㅠㅠ

---

💭 풀이

• dp 배열은 각 노드에서 최대 가중치의 합을 저장한다. dp[i][0]은 i번 노드를 포함하지 않을 때의 최대 합, dp[i][1]은 i번 노드를 포함할 때의 최대 합을 의미하게 된다.
• 동시에 path배열은 해당 조건에서의 최적 경로를 저장하는데 만약 s의 자식노드 i가 속해있는 dp[i][1]이 dp[i][0]보다 크다면 dp[s][0]은 당연히 가중치가 큰 dp[i][1]을 더해주고 path[s][0]은 path[i][1] 배열을 더해주게 된다. 만약 반대 상황이라면 [i][0]의 값을 더해주게 될테다.
• dp[s][1]과 path[s][1]은 항상 s번 노드를 포함하는 배열이기 때문에 자식노드들이 포함되지 않는 [i][0]의 값들을 더해주게 된다.
• 그렇게 dfs를 통해 만들어진 dp와 path는 0이 있거나 0이 없거나의 두 사건 중 더 큰 가중치를 가지고 있는 값을 출력할 수 있게 된다.

---

💻 코드

import sys
input = sys.stdin.readline

def dfs(s) :
    check[s] = True
    dp[s][1] = weight[s]
    path[s][1] = [s]

    for i in tree[s] :
        if not check[i] :
            dfs(i)
            if dp[i][1] >= dp[i][0] :
                dp[s][0] += dp[i][1]
                path[s][0] += path[i][1]
            else :
                dp[s][0] += dp[i][0]
                path[s][0] += path[i][0]
            dp[s][1] += dp[i][0]
            path[s][1] += path[i][0]


n = int(input())
weight = [0] + list(map(int,input().split()))
dp = [[0,0] for _ in range(n+1)]
check = [False]*(n+1)
path = [[[] for _ in range(2)] for _ in range(n+1)]
tree = [[] for _ in range(n+1)]

for _ in range(n-1) :
    a, b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

dfs(1)

if dp[1][0] > dp[1][1] :
    print(dp[1][0])
    path[1][0].sort()
    print(*path[1][0])
else :
    print(dp[1][1])
    path[1][1].sort()
    print(*path[1][1])

---