[BOJ] Q1949 우수마을

[BOJ] Q1949 우수마을

Question

Language: Python

Difficulty: Gold 2

해당 문제는 2533와 비슷한 유형의 문제로 Tree에서 Dynamic Programming을 적용하는 문제이다. Root node로부터 순회를 시작해서 기존에 저장된 중간값을 활용해서 최대값을 구해가는 과정의 문제이다. Tree에서의 DP라고해서 막연하게 어려운 것이 아니라, DFS + visited 처리를 통해 Tree 순회를 통해 DP를 수행하면 된다.

1. vertex가 우수마을 인 경우, 인접한 마을에 대해서는 우수마을이 되어서는 안된다.

   dp[vertex][1]+=dp[child][0]
   

2. vertex가 우수마을이 아닌 경우, 인접한 마을은 우수마을 이거나, 우수마을이 아닐 수도 있다.

   dp[vertex][0]+=max(dp[child])
   

자식 노드에서부터 최대값을 고려하면서 root 노드까지 순회를 진행하기 때문에, 3번 조건은 만족할 수 밖에 없다. 최대값을 저장하기 때문에, 인접한 노드가 모두 우수마을이 아닌 경우가 발생하지 않는다는 것을 통해 3번 조건이 자동으로 성립되는 것을 인지하는 것이 중요하다.

Solution

import sys
def solution(vertex):
    visited[vertex]=True
    for child in graph[vertex]:
        if visited[child]:
            continue

        solution(child)
        dp[vertex][1]+=dp[child][0]
        dp[vertex][0]+=max(dp[child])

    return max(dp[vertex])

if __name__ == "__main__":
    sys.setrecursionlimit(10**5)
    n=int(input())
    peoples=list(map(int,input().split()))
    graph=[[] for _ in range(n)]
    dp=[[0,peoples[i]] for i in range(n)]

    visited=[False] * n

    for i in range(n-1):
        v1,v2=map(lambda x: int(x)-1,input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    result=solution(0)
    print(result)