백준 2533번 : 사회망 서비스(SNS) in Python

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

 

www.acmicpc.net

이 문제는 트리로 나타낼 수 있는 친구 관계에서 모든 개인이 새로운 아이디어를 수용하기 위한 최소 얼리 어답터의 수를 구하는 문제로, 얼리 어답터가 아닌 사람이 새로운 아이디어를 수용하기 위해서는 그 사람과 인접한 사람들이 모두 얼리 어답터여야 한다.

이 문제는 이전의 트리의 독립집합 문제와 유사한 방법으로 해결할 수 있다. 다만, 각 노드마다 자신이 얼리 어답터가 되는 경우와 그렇지 않은 경우로 나눠서 dynamic programming을 적용한다. 각 노드 u마다 자신이 얼리 어답터가 되는 경우 u를 루트로 하는 서브트리에서 u의 각 자식 노드가 얼리 어답터가 되든 안 되든 상관없으므로 두 경우 중 최소가 되는 얼리 어답터의 수를 u의 얼리 어답터의 수에 더한다. u가 얼리 어답터가 아닌 경우 u와 인접한 모든 노드들이 얼리 어답터여야 하므로 u의 각 자식 노드가 얼리 어답터가 될 때 최소가 되는 얼리 어답터 수를 u의 얼리 어답터의 수에 더한다.

base case인 leaf 노드의 경우에는 자신이 얼리 어답터가 되는 경우와 그렇지 않은 경우는 각각 얼리 어답터의 수가 1, 0이 될 것이다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
visited = [False for _ in range(n+1)]
# 최소가 되는 얼리 어답터의 수를 두 가지 경우로 나눠 저장한다.
# 앞의 수는 자신이 얼리 어답터가 되는 경우, 뒤의 수는 자신이 얼리 어답터가 아닌 경우이다. 
dp = [[1, 0] for i in range(n+1)]
def DFS(currNode):
    visited[currNode] = True
    for v in graph[currNode]:
        if not visited[v]:
            DFS(v)
            dp[currNode][0] += min(dp[v][1], dp[v][0])
            dp[currNode][1] += dp[v][0]
            
DFS(1)
print(min(dp[1][0], dp[1][1]))