[BOJ] 2533. 사회망 서비스

문제 링크

import sys
sys.setrecursionlimit(10**9)

input = sys.stdin.readline 

n = int(input())
graph  = [[] for _ in range(n + 1)]
visited = [False] * (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)]

def solve_dp(num):
  visited[num] = True
  dp[num][0] = 0
  dp[num][1] = 1 # 자신 포함시키기(얼리어답터 수)

  for i in graph[num]:
    if not visited[i]:
      solve_dp(i)
      dp[num][0] += dp[i][1]
      dp[num][1] += min(dp[i][0], dp[i][1])

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

문제 접근

DP를 이용한다.
1. dp[index][1]
정점 번호가 index이고 자신이 얼리어답터인 경우
이 경우는 자식 노드가 얼리 어답터일 때와 아닐 때를 구분해서 그 중 작은 값을 더하면 된다.

2. dp[index][0]
정점 번호가 index이고 자신이 얼리어답터가 아닌 경우
이 경우는 자식 노드가 무조건 얼리어답터이어야 하기 때문에 dp[i][1]을 더해준다.

이때 자식 노드를 접근할 때 재귀함수를 이용한다.

sys.setrecursionlimit

python은 재귀제한이 걸려있어서 재귀 허용치가 넘어가면 런타임에러를 일으킨다.
->sys.setrecursionlimit(10**9) 작성
기본적으론 1000 이다

14번이나 시도했다. 트리 DP 기억해야지..