백준 #2533 사회망 서비스(SNS)

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(node, parent):
	dp[node][1] = 1
	for nxt in graph[node]:
		if nxt == parent:
			continue
		dfs(nxt, node)
		dp[node][0] += dp[nxt][1]
		dp[node][1] += min(dp[nxt][0], dp[nxt][1])


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


# dp[i][0]: i번째 노드가 얼리어댑터가 아닌 경우
# dp[i][1]: i번째 노드가 얼리어댑터인 경우
dp = [[0, 0] for _ in range(n + 1)]

dfs(n, -1)

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

풀이

트리구조에다가 dp를 적용시킨 문제이다.

$dp[i][0]$ 를 i번째 노드가 얼리어댑터가 아닌경우,

$dp[i][1]$을 i번째 노드가 얼리 어댑터인 경우의 수로 지정해준 뒤 풀었다.

루트노드가 딱히 지정된게 없어서 1~n 중 아무 번호로 시작해도 된다.

대신 마지막 출력을 해줄 때에는 모든 경우의 수가 합쳐진 루트노드를 출력해주어야한다.