[ 2533 ] [ Tree + DP ] 사회망 서비스(SNS)

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

2533번: 사회망 서비스(SNS)

---

풀이 과정

---

1. 아무 점이나 루트로 잡아서 진행한다.
2. 현재 점에 연결된 방문하지 않은 모든 점들을 방문하면서 DP테이블을 갱신한다.
   1. 초기 모든 DP테이블은 점마다 [0, 1]로 설정한다.  
   2. DP[i][0]은 루트가 i점인 부분 트리에서 i점이 얼리어답터가 아닐 때의 전체 얼리어답터 최소 개수
   3. DP[i][1]은 루트가 i점인 부분 트리에서 i점이 얼리어답터일 때의 전체 얼리어답터 최소 개수
   4. 따라서, DP[i][0]은 다음 점에서는 얼리어답터가 나와야 하므로 DP[다음 점][1]을 더해준다.
   5. DP[i][1]은 다음 점에서 얼리어답터가 나올수도 있고 나오지 않을수도 있으므로 DP[다음 점][0]과 DP[다음 점][1]의 최솟값을 더해 준다.
3. 루트 노드에서의 DP 테이블의 최솟값을 출력시켜준다.

---

소스 코드

---

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
tree = [[] for _ in range(n+1)]

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

root = 1

dp = [[0, 1] for _ in range(n+1)]
visited = [False] * (n+1)

def solve(node):
    visited[node] = True
    for next_node in tree[node]:
        if not visited[next_node]:
            solve(next_node)
            dp[node][0] += dp[next_node][1]
            dp[node][1] += min(dp[next_node][0], dp[next_node][1])
        

solve(root)
print(min(dp[root]))