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

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

---

 

24/03/30

 

 

예전에 해결했던 문제인데, 복습하는 겸 글을 적어본다.

---

 

문제 접근 방식:

 

 

문제의 요구사항은 트리가 주어질 때 얼리 어답터의 수를 최소화하는 문제다.

 

얼리 어답터가 아닌 사람들은 주변의 모든 사람들이 얼리어답터인 경우에 아이디어를 수용한다. 목표는 모든 사람이 아이디어를 수용하도록 하고 싶을 때, 얼리 어답터의 수를 최소화하는 것이다.

 

전형적인 트리 DP로 해결할 수 있는데, 다음과 같이 DP테이블을 정의하자.

 

$DP[i][0]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$번째 노드가 얼리 어답터가 아닐 때 서브 트리 전체의 최소 얼리 어답터 수

$DP[i][1]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$번째 노드가 얼리 어답터일 때, 서브 트리 전체의 최소 얼리 어답터 수

 

이 DP테이블에 따르면 다음과 같이 점화식을 세울 수 있다.

 

만약 자기 자신이 얼리 어답터가 아니라면 자신 밑의 모든 노드들은 얼리어답터여야 한다.

 

따라서, $DP[i][0] = \text{sum}(DP[\text{below}][1])$이 된다.

 

자신이 얼리 어답터라면, 자식 노드가 얼리 어답터가 되든 얼리 어답터가 안되는 간에 상관이 없다. 따라서 둘 중 최소를 취해주면 된다.

 

$DP[i][1] = \text{sum}(\min(DP[\text{below}][0], DP[\text{below}][1]))$

 

이를 토대로 탑다운 DP를 돌리면 된다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2533번 사회망 서비스(SNS)
# tree DP
'''
접근 방법:
DP[i][0] = i번째 노드가 서브트리의 노드고 i번째 노드가 얼리어답터가 아닐때 드는 최소 비용
DP[i][1] = i번째 노드가 서브트리의 노드고 i번째 노드가 얼리어답터 일때 드는 최소 비용
자신이 얼리 어답터가 아니면, 자신의 밑에 있는 모든 노드들은 얼리어답터여야 함.
DP[i][0] = sum(DP[below][1])
자신이 얼리 어답터라면 자식노드는 노상관
DP[i][1] = sum(min(DP[below][0], DP[below][1]))
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1_000_020)

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)
DP = [[0, 0] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
def dfs(i):
    visited[i] = 1
    for below_node in tree[i]:
        if visited[below_node] == 0:
            dfs(below_node)
            DP[i][0] += DP[below_node][1]
            DP[i][1] += min(DP[below_node][0], DP[below_node][1])
    DP[i][1] += 1

dfs(1)
print(min(DP[1]))