[백준] 사회망 서비스(SNS)

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

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

트리 DP 문제입니다. 리프노드부터 탐색하면서 현재 노드가 얼리어답터인 경우와 그렇지 않은 경우 가질 수 있는 최소값을 DP 배열에 기억해놓으면 됩니다. 현재를 얼리어답터로 만드는 경우에는 자식 노드들이 얼리어답터여부에 상관없이 최소값만의 합을 구하고 현재를 얼리어답터로 만들지 않는 경우에는 무조건 자식들이 얼리어답터여야합니다. 이렇게 해서 루트 노드인 1가 얼리어답터인 경우 그렇지 않은 경우 둘 중 최소값을 출력해주면 됩니다.

 

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 8)

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

INT_MAX = sys.maxsize

graph = defaultdict(list)

n = int(input())

for _ in range(n - 1):
    a, b = tuple(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)


dp = [
    [INT_MAX] * (n + 1)
    for _ in range(2)
]

visited = [False] * (n + 1)

def dfs(cur):
    clist = []
    for next in graph[cur]:
        if not visited[next]:
            visited[next] = True
            clist.append(next)
            dfs(next)

    # 현재를 얼리어답터로 만드는 경우
    sum1 = 1
    # 현재를 얼리어답터로 만들지 않는 경우
    sum2 = 0
    for node in clist:
        # 현재를 얼리 어답터로 만들면 둘 중 최소를 택한다.
        sum1 += min(dp[0][node], dp[1][node])
        sum2 += dp[1][node]

    dp[1][cur] = sum1
    dp[0][cur] = sum2


visited[1] = True
dfs(1)

print(min(dp[1][1], dp[0][1]))