백준 2533 - 사회망 서비스(SNS) [Python]

문제

• 입력
  첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에지 (u, v)를 나타내는 두 정수 u와 v가 하나의 빈칸을 사이에 두고 주어진다.
• 출력
  주어진 친구 관계 그래프에서 아이디어를 전파하는데 필요한 얼리 아답터의 최소 수를 하나의 정수로 출력한다.

---

풀이

예제 1 풀이

DP[N][2] 테이블을 만들어서 풀어보자.

• DP[i][0]: i번째 노드가 얼리어답터인 경우, 본인 + 하위 노드들에서 나올 수 있는 얼리어답터 수의 최소값
  → DP[i][0] = sum(min(DP[j][0], DP[j][1]) for j in i's children)
• DP[i][1]: i번째 노드가 일반인인 경우, (본인 제외) 하위 노드들에서 나올 수 있는 얼리어답터 수의 최소값
  → DP[i][1] = sum(DP[j][0] for j in i's children)

위의 트리 그래프에서

• ③, ⑤, ⑥ 등의 리프 노드들은 얼리어답터일 수 있는 하위 노드들이 없으므로 DP[i][0] = 1, DP[i][1] = 0이다.
• ②, ④의 경우
  • 본인이 얼리어답터인 경우, 하위 노드들은 얼리어답터일 필요가 없기 때문에 DP[i][0] = 1(본인)+0+0 = 1이다.
  • 본인이 얼리어답터가 아닌 경우, 하위 노드들이 모두 얼리어답터야 하므로 DP[i][1] = 1+1 = 2이다.
• ①의 경우
  • 본인이 얼리어답터인 경우, ③은 얼리어답터일 필요가 없고 ②와 ④는 얼리어답터일 때 가질 수 있는 얼리어답터 수가 최소가 될 수 있으므로 DP[1][0] = 1(본인)+1+0+1 = 3이다.
  • 본인이 얼리어답터가 아닌 경우, 하위 노드들이 모두 얼리어답터야 하므로 DP[1][1] = 1+1+1 = 3이다.

예제 2 풀이

---

코드

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

N = int(input())
G = [[] for _ in range(N+1)]

for _ in range(N-1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

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

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

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

• pypy로 제출했을 때는 메모리 초과가 터져서 Python으로 제출해서 통과했다.