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

   문제

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

가장 많은 독립집합을 찾는 문제라고도 볼 수 있을거 같다.

가장 많은 독립집합을 구한 후 독립집합을 연결하는 노드가 얼리아답터라고 볼수있다.

즉 가장 많은 독립집합을 만드는 경우를  찾은 후 전체 노드의 수에서 빼주면 얼리 아답

터의 최소수가 된다.이전문제처럼 DFS를 사용해 가장 하단의 노드부터 차례대로 해당

노드가 포함되었을때와 포함되지 않았을때 독립집합이 가장 많이 경우를 DP를 통해

구하면 된다.

import sys
sys.setrecursionlimit(10**9)
 
N=int(sys.stdin.readline())
Tree=[[] for _ in range(N+1)]
check=[0 for _ in range(N+1)]
for _ in range(N-1):
    u,v=map(int,sys.stdin.readline().split())
    Tree[u].append(v)
    Tree[v].append(u)
DP=[[0,0] for _ in range(N+1)]
 
check=[True for _ in range(N+1)]
def DFS(cur):
    check[cur]=False#방문체크
    DP[cur][0]=1#현재 노드 포함할때
    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])#현재노드를 포함 안했을때
 
DFS(1)
print(N-max(DP[1][0],DP[1][1]))