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

문제

---

풀이

 

DFS + DP로 풀이하는 문제이다.

 

얼리 어답터가 아닌 노드의 이웃은 반드시 얼리 어답터여야 하는 상황에서, 친구 관계 그래프가 트리 형태로 한정된다는 점을 최대로 이용, 즉 서브트리(subtree) 단위로 생각하는 것이 좋다. 따라서

• 사람들은 모두 얼리 어답터이거나 얼리 어답터가 아니고,
• 얼리 어답터의 자식 노드는 얼리 어답터일 수도, 아닐 수도 있으며,
• 얼리 어답터가 아닌 사람의 자식 노드는 무조건 얼리 어답터여야 한다.

위 핵심 아이디어를 가지고 점화식을 세워 트리에서의 DP로 풀이한다.

• \(dp[u][0] =\sum{dp[v][1]}\)
• \(dp[u][1]=1+\sum{min(dp[v][0], dp[v][1])}\)

이에 기반한 핵심 로직은 아래와 같다.

dp = [[0, 0] for _ in range(N + 1)]

def dfs(u, parent):
    dp[u][0] = 0
    dp[u][1] = 1 

    for v in graph[u]:
        if v == parent: continue
        dfs(v, u)

        dp[u][0] += dp[v][1]
        dp[u][1] += min(dp[v][0], dp[v][1])

무방향 트리이므로 부모 노드를 별도로 명시해주어야 한다. 따라서 dfs에 parent 인자도 함께 전달하였다.

위 점화식과 동일하게,

• u가 얼리 어답터인 경우 자식 노드도 모두 얼리 어답터이므로 자식 노드 v가 얼리 어답터인 경우의 개수(dp[v][1])를 dp[u][0]에 더해 주고,
• u가 얼리 어답터가 아닌 경우 자식 노드가 얼리 어답터인 경우/아닌 경우들 중 최솟값을 dp[u][0]에 더한다.

 

이후 루트 노드(index=1)가 얼리 어답터인 경우와 아닌 경우 중 필요한 얼리 어답터 수가 적은 것을 답으로 출력하면 끝

---

전체 코드

 

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

N = int(input())    # 노드(1-based)
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)

dp = [[0, 0] for _ in range(N + 1)]
# dp[i][0] = 노드 i가 얼리 어답터가 아닐 때 i의 서브트리에서 필요한 얼리 어답터 수
# dp[i][1] = 노드 i가 얼리 어답터일 때 ~ 

def dfs(u, parent):
    dp[u][0] = 0
    dp[u][1] = 1    # u가 얼리 어답터

    for v in graph[u]:  # v = 자식 노드
        if v == parent: continue
        dfs(v, u)

        dp[u][0] += dp[v][1]    # u가 얼리 어답터가 아니면 자식은 반드시 얼리 어답터
        dp[u][1] += min(dp[v][0], dp[v][1]) # u가 얼리 어답터면 자식은 얼리 어답터일 수도 아닐 수도 -> 최솟값 선택

dfs(1, 0)   # 루트 노드
print(min(dp[1][0], dp[1][1]))

pypy3으로는 메모리 초과 오류 발생