[다이나믹 프로그래밍/파이썬] 백준 2533번 : 사회망 서비스(SNS) / 골드 3

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

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

import sys
sys.setrecursionlimit(10**7)
n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

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

def dfs(node):
    for next in graph[node]:
        if not visited[next-1]:
            visited[next-1] = True
            dfs(next)
            dp[node-1][0] += dp[next-1][1]
            dp[node-1][1] += min(dp[next-1])

visited[0] = True
dfs(1)
print(min(dp[0]))

트리 dp는 처음 풀어보았다.

트리 dp의 접근은 dfs로 할 수 있다.

어차피 방문 체크를 하며 탐색을 하면 dfs를 해도 트리 노드를 아래 방향으로 내려가며 탐색할 수 있게 된다. 어차피 위로는 부모 노드이고 이미 방문 체크가 되어있기 때문이다.

 

그러면서 트리 dp를 dp[i][j]로 구성한다. i는 노드번호, j는 0이면 얼리어답터가 아닌 경우, 1이면 얼리어답터인 경우다.

 

내가 얼리어답터가 아니려면 내 자식 노드는 모두 얼리어답터여야한다. => 자식이 얼리어답터일 때의 값을 취함

내가 얼리어답터라면 내 자식이 얼리어답터이건 아니건 상관이 없다. => 최솟값을 취함

 

위와 같은 방식을 반복하며 루트 노드까지 올라가면 된다.