[Python]트리에서의 동적 계획법 백준 2213

   문제

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

트리에서 DP를 사용하는 문제이다.

DFS 후위순회를 통해 가장 아래의 노드부터 현재노드가 포함되었을때와 그렇지 않을때

의 값을 둘다 저장하면서 루트노드까지 올라가는 방식으로 구현하였다.

재귀를 통해 구현하였으며 독립집합의 최대값을 구한뒤 그 값을 이용하여 추적하는 

함수도 따로 구하였다.

예제를 살펴보면

7

10 30 40 10 20 20 70

1 2

2 3

4 3

4 5

6 2

6 7

먼저 루트를 1로하는 트리로 만들어 준 뒤 후위순회를 통해 노드 순서를 살펴보면

 5->4->3->7->6->2->1 순으로 DP를 수행하면된다.

5번노드의 DP값은 5번노드가 포함되었을때 DP[5][0]=20,5번노드가 포함되지 않았을때

 DP[5][1]=0을 저장한다.

 4번노드.현재노드를 포함시킨다면  자식노드들을 포함시킬수 없으므로 현재노드값 +자

식들이 포함되지 않았을때의 최대값을 더해주면된다.  DP[4][0]=10+(DP[i][1] for i in 자

식들)이다.

4번노드가 현재값을 포함시키지 않는다면 자식노드들이 포함되었을때의 최대값과 포함

되지 않았을때의 최대값들중 큰값을 더해주면된다.

 DP[4][1]=0+(max(DP[i][0],DP[i][1]) for i in 자식들) 이다.

이런식으로 차례대로 재귀와 DP를 이용해 구현해 주면된다.

추적의 경우에는 DP를 통해 루트에서 부터 이전노드의 포함여부를 통해 이전노드가 

포함되었다면 현재노드를 포함하지 않는것이고 포함되지 않았다면 현재노드의 DP값에

서 큰값에 따라 현재노드가 포함되는지 안되는지의 여부를 알아볼수있다.DP[i][0]이 더

크다면 현재노드는 포함되는것이고 결과값에 추가해주고 자식노드에서 반복해주면

되고 DP[i][1]이 더크다면 현재노드를 추가하지않고 자식노드에서 똑같이 수행해주면된다.

import sys
n=int(sys.stdin.readline())
node_value=[0]+list(map(int,sys.stdin.readline().split()))
Tree=[[] for _ in range(n+1)]
DP=[[0,0] for _ in range(n+1)]
 
for _ in range(n-1):#간선받기
    a,b=map(int,sys.stdin.readline().split())
    Tree[a].append(b)
    Tree[b].append(a)
 
 
 
check=[True for _ in range(n+1)]
def DFS(cur):
    check[cur]=False#방문체크
    DP[cur][0]=node_value[cur]#현재 노드 포함할때
    DP[cur][1]=0#현재 노드 포함하지 않을때
    for i in Tree[cur]:#연결된 노드 탐색
        if check[i]:#방문할수 있다면
            DFS(i)
            DP[cur][0]+=DP[i][1]#해당노드 포함했을때
            DP[cur][1]+=max(DP[i][0],DP[i][1])#해당노드 포함 안했을때
 
 
trace_result=[]
trace_check=[True for _ in range(n+1)]
def Trace(cur,pre):#현재노드와 이전노드가 포함되었는지 안되었는지 0:포함됨 1:포함안됨
    trace_check[cur]=False
 
    if pre==0:#이전노드가 포함되었다면
        for i in Tree[cur]:#현재노드는 포함할수없음
            if trace_check[i]:
                Trace(i,1)
    else:#이전노드가 포함되어있지않다면
        if DP[cur][0] > DP[cur][1]:  # 현재노드를 포함한 부분이 더크다면
            trace_result.append(cur)  # 현재노드 포함
            for i in Tree[cur]:
                if trace_check[i]:
                    Trace(i, 0)
        else:  # 현재노드를 포함하지 않은부분이 크다면
            for i in Tree[cur]:
                if trace_check[i]:
                    Trace(i, 1)
 
 
 
DFS(1)
print(max(DP[1][0],DP[1][1]))
Trace(1,1)#임의의 루트노드지정 ,이전노드가 없으므로 1로 둔다
trace_result.sort()#오름차순정렬
print(*trace_result)