백준 1949번: 우수 마을 (Python)

접근

이전에 풀었던 트리의 독립집합 문제와 매우 유사한 문제였다.

유사 문제: 2021.05.05 - [코딩/백준 (Python)] - 백준 2213번: 트리의 독립집합 (Python)

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

가중치가 없고, 각각의 마을들을 출력하지 않아 오히려 코드가 더 심플해졌다.

코드

import sys

sys.setrecursionlimit(10 ** 9)
n = int(sys.stdin.readline())
population = [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)]


def dfs(start):
    visited[start] = 1
    dp[start][0] = population[start]
    for i in lines[start]:
        if not visited[i]:
            dfs(i)
            dp[start][0] += dp[i][1]
            dp[start][1] += max(dp[i][1], dp[i][0])


dfs(1)
print(max(dp[1][0], dp[1][1]))

더 생각해 볼 것?

...

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