[PS | 한 번에 맞자!] 백준 1949

0. 문제

우수 마을

1949번: 우수 마을

---

1. 문제 생각

트리에서의 DP 문제이다. 

트리란
사이클이 없이 모든 정점이 연결되어있는 그래프로, 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개라는 특징을 갖는다.

DFS+DP 로 트리에서의 DP를 해결할 수 있고 아래처럼 DP 테이블을 채우기 위해 계속해서 인접한 노드를 탐색하는 점에서 DFS가 강력하다!

---

2. 문제 구현

import sys
sys.setrecursionlimit(10**6)

def dfs(n):
    visited[n]=1
    DP[n][1]=List[n]
    for i in node[n]:
        if visited[i]: continue
        dfs(i) #해당 노드 처리
        #
        DP[n][0]+=max(DP[i][0],DP[i][1])#주변꺼에서 아닌 곳, 또는 주변꺼에서 맞는 곳
        DP[n][1]+=DP[i][0]
        
N=int(input())
List=list(map(int,input().split()))
List=[0]+List
node=[[] for _ in range(N+1)]
visited=[0 for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
DP=[[0 for _ in range(2)] for _ in range(N+1)]

dfs(1)
# print(DP)
print(max(DP[1]))

---

3.
아이디어 생각? X
한 번에 풀었는가? X