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

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

 

 

 

코드

import sys
sys.setrecursionlimit(10**9)
def dfs(node):
	visit[node] = 1
	for i in graph[node]:
		if visit[i] == 0:
			dfs(i)
			dp[node][0] += min(dp[i][0],dp[i][1])
			dp[node][1] += dp[i][0]

n = int(input())
graph = [[] for _ in range(n+1)]
dp = [[1,0] for _ in range(n+1)]
visit = [0] * (n+1)
for _ in range(n-1):
	a,b = map(int,sys.stdin.readline().split())
	graph[a].append(b)
	graph[b].append(a)

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

 

설명

dp를 이용해서 dp[i][0]은 i번째 노드가 얼리 아답터인 경우 해당 서브트리에서 얼리 아답터의 최솟값을 넣은 값이고, dp[i][1]은 
i번째 노드가 얼리 아답터가 아닌 경우의 최솟값을 넣은 값이다.
dp[i][0]의 경우는 자신이 얼리 아답터이기 때문에 초기값은 모두 1로 두었다.
dp[i][1]의 경우 자신이 얼리 아답터가 아니기 때문에 자식 노드가 무조건 얼리 아답터여야 한다.