[백준] 2533 사회망 서비스

---

DFS를 사용한다는 것 말고는 제대로된 접근도 하지 못한 문제이다.

 

임의의 한 노드를 얼리어답터로 할 것인지 하지 않을 것인지 기준을 잡는 것이 중요하다.

 

1. 현재 노드가 얼리어답터일 경우: 자식 노드는 얼리어답터일 수도 아닐 수도 있다.

2. 현재 노드가 얼리어답터가 아닐 경우: 자식노드는 반드시 얼리어답터이어야 한다.

 

다음으로는 점화식을 만들어야 한다. 얼리어답터인 경우를 0, 그렇지 않을 경우를 1로 하고 2차원 배열을 선언한다.

DP 노드는 현재 노드가 얼리어답터일 경우 최소 얼리어답터 수와 현재 노드가 얼리어답터가 아닐 경우 얼리어답터의 최소 수를 담고 있다.

 

DP[node][0] = 0 : node는 얼리어답터가 아니다

DP[node][1] = 1 :  node는 얼리어답터 이다.

 

점화식

DP[parent][0] += DP[child][1] 

DP[parent][1] += Min(DP[child][0], DP[child][1])

 

from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
readline = stdin.readline


N = int(readline())
tree = [[] for _ in range(N+1)]
dp = [[0, 1] for _ in range(N+1)] # 0: 노드가 얼리어답터가 아닐때, 1: 노드가 얼리어답터일 때
visited = [False] * (N+1)

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

def dfs(cur):
    visited[cur] = True
    
    for child in tree[cur]:
        if not visited[child]:
            dfs(child)
            # 현재 노드가 얼리어답터가 아닐 경우
            # 반드시 자식노드가 얼리어답터 이어야 한다. 
            dp[cur][0] += dp[child][1]
            # 현재 노드가 얼리어답터일 경우
            # 자식 노드는 얼리어답터일 수도 아닐 수도 있다.
            dp[cur][1] += min(dp[child])


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