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

문제

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

분석

얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다고 할 때, 필요한 최소 얼리 어답터의 수를 구하는 문제이다.

트리에서는 사이클이 없기 때문에 dfs를 이용하면 한 방향으로 쭉 갈 수 있다.

트리의 노드가 각각 얼리어답터인지, 아닌지로 두 가지의 상태를 가질 수 있다. 따라서 dp배열을
'dp[현재 노드][얼리어답터 여부] = 최소 얼리어답터' 로 나타낼 수 있다.
만약 현재 노드가 얼리어답터가 아니라면, 연결된 노드는 모두 얼리어답터여야 한다.
만약 현재 노드가 얼리어답터라면, 연결된 노드는 얼리어답터여도 아니여도 된다. 따라서 그 두 경우중 작은 것을 택하면 된다. 그리고 마지막에 현재 노드가 얼리어답터이므로 +1을 해준다.

dfs에서 연결된 노드가 없으면 현재 노드의 상태를 두가지로 나누어 저장해둔다.
주의할 것은 dfs가 깊이 탐색이 먼저 진행되고 dp배열에 값을 채워지며 dp[root]까지 값이 채워져야 한다.

이 문제에서 루트는 정해지지 않는다. N이 최소 2이기 때문에 1이나 2를 root로 정해서 dp배열을 채워 나가면 된다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v = map(int, input().split())
    tree[u].append(v)
    tree[v].append(u)
visited = [False] * (n+1)
dp = [[0, 0] for _ in range(n+1)]

def dfs(x):
    visited[x] = True
    if tree[x]:
        for nx in tree[x]:
            if not visited[nx]:
                dfs(nx)
                dp[x][0] += dp[nx][1]
                dp[x][1] += min(dp[nx][0], dp[nx][1])
        dp[x][1] += 1
    else:
        dp[x][0] = 0
        dp[x][1] = 1

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

끝으로..

트리에서 dp문제를 처음 접해봤는데, 생각보다 복잡하지는 않았다. 관련 문제를 더 접해봐야겠다.