[python] 백준 1949 우수 마을

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

1949번: 우수 마을

문제 해결

• 이웃한 마을, 즉 연결되어있는 지역으로 가면 안된다는 것이 어려운 부분이다.
• 이를 dp[i][0], dp[i][1] 로 두가지로 나눠서 i번째 마을을 포함하지 않은 누적 최대합과 i번째 마을을 포함하는 누적 최대합으로 나눠서 계산을 한다.
• 그럼 어떻게 모든 마을의 경우의 수를 계산하는가? dfs(깊이 우선 그래프)를 이용해 모든 마을을 순찰하면서 최대 합을 구할 수 있다.
• visited를 통해 한번 지나간 마을은 다시 지나가지 않는다.
• 마을i에 왔을 때 다음 연결된 마을을 next라고 하자. 그러면 dp[i][1] += dp[i][0]이고 dp[i][0] += max(dp[i][0], dp[i][1]) 이 된다.
• 양방향이기 때문에 어디 마을부터 시작해도 상관없지만 1번마을부터 시작하여 누적 합 최대 max(dp[1][0], dp[1][1])을 구한다.
•  

CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(num):
    visited[num] = 1
    for next in graph[num]:
        if not visited[next]:
            dfs(next)
            dp[num][1] += dp[next][0]
            dp[num][0] += max(dp[next][0], dp[next][1])
if __name__=='__main__':
    n = int(input())
    people = [0]+list(map(int, input().split()))
    visited = [0]*(n+1)
    dp = [[0,people[i]]*2 for i in range(n+1)]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        s, e = map(int, input().split())
        graph[s].append(e)
        graph[e].append(s)
    dfs(1)
    print(max(dp[1][1],dp[1][0]))