BaekJoon 1949번 : 우수 마을 (python)

📝 BaekJoon 1949번 : 우수 마을 (G2 53.907%)

---

🔎 우수 마을 문제

---

📌 아이디어

트리에 조건이 달린 DP를 응용한 문제이다.

---

💭 풀이

• 문제의 조건 1,2,3을 보면 1에서는 DP를 이용한 최대값을 이야기하고, 2에서는 '우수 마을'끼리는 인접할 수 없고, 3에서는 '우수 마을'이지 않은 마을은 최소 하나 이상의 '우수 마을'과 인접 해야한다는 조건을 가지고 있다.
• 해당 조건을 DP로 구현할 때 DP[node][0]을 node가 '우수 마을'이 아닐 때, DP[node][1]을 node가 '우수 마을'일 때로 가정해본다.
• 만약 해당 node가 '우수 마을'이라면 조건 2에 따라 해당 노드의 주민 수 + 인접 노드들이 '우수 마을'이지 않아야 한다. 만약 해당 node가 '우수 마을'이지 않으면 인접한 마을들이 '우수 마을'일 수도 있고 아닐 수도 있는 두 경우의 수에서 더 큰 값을 더하게 된다. 왜냐하면 만약 DP[i][1]이 더 크다고 하면 다이렉트로 조건 3을 만족하고 만약 DP[i][0]이 더 큰 값이라고 하면 node에 인접한 i마을들 중 적어도 하나는 '우수 마을'과 인접하도록 보장하게 된다. DP[i][1] < DP[i][0]일 경우는 i가 우수 마을이 되어야 할 상황을 최적화하여 포함시키는 경우의 수를 의미하게 된다.

---

💻 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

    for i in tree[s] :
        if not check[i] : 
            dfs(i)
            dp[s][0] += max(dp[i][1],dp[i][0])
            dp[s][1] += dp[i][0]

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

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

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

---