[Python] 백준 / gold / 2533 : 사회망 서비스

문제 링크 : https://www.acmicpc.net/problem/2533

트리에서의 다이나믹 프로그래밍문제. 다행히 난 아직 다이나믹 프로그래밍은 점화식을 설정하는 게 중요하다는 걸 기억하고 있다.. 이 문제에서 dp[x] 는 이렇게 설정했다.

dp[X] = (X를 루트노드로 갖는 서브 트리에서, 최소 얼리 어덥터의 수)
점화식은 아래처럼 세울 수 있었다.

if (dp[X] 의 child 가 모두 어덥터라면)
	dp[X] = dp[child1] + dp[child2] + .. dp[child마지막]
    
else (dp[X] 의 child 가 모두 어덥터인 것은 아니라면)
	// -> X도 어덥터가 되어야 하므로 1을 더해준다.
	dp[X] = dp[child1] + dp[child2] + .. dp[child마지막] + 1
    

dfs 로 모든 트리를 탐색했고, dfs 의 리턴값은 본인이 어덥터가 되는지로 설정했다. 그리고 이 문제의 경우, 탐색을 어떤 노드에서부터 시작하던지 상관 없기 때문에 1번 노드부터 탐색을 시작했다.

기억할 것

1. 트리 DP 에서, dp[i] = ( i 를 루트 노드로 가지는 서브 트리에서 ~ )로 설정하는게 좋다.

2. 트리 간선을 양방향으로 설정했다면, 꼭 루트노드부터 탐색을 시작할 필요는 없다.

3. 트리의 개념을 확실히 해야한다. 크리스마스 트리처럼 이쁘게 생긴 트리만 트리로 생각할게 아니라, 사이클이 없는 그래프를 트리라고 한다.

4. (트리에서 간선의 개수) = V-1

5. 트리에서 임의의 두 노드 사이의 경로는 오직 한 개 존재한다.

파이썬 코드

import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
tree = [[] for _ in range(N+1)]
# dp[x] = [n, q]
# n = x를 루트로 하는 서브트리에서의 최소 어덥터 수
# q = 루트 x가 어덥터인지 여부
dp = [-1] * (N+1)
visit = [False] * (N+1)
in_degree = [0] * (N+1)
root = 1

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


# 리턴 값은 현재 노드가 어댑터가 될 것인지
def dfs(node):
    visit[node] = True

    # 만약 현재 노드가 리프라면
    if not tree[node]:
        dp[node] = 0
        return False

    # 현재 노드가 리프가 아니라면
    all_children_is_adapter = True
    dp[node] = 0
    for child in tree[node]:
        if not visit[child]:
            result = dfs(child)
            dp[node] += dp[child]
            if not result:
                all_children_is_adapter = False

    if all_children_is_adapter:
        return False
    else:
        dp[node] += 1
        return True


dfs(root)
print(dp[root])