[골드3] 2533번 : 사회망 서비스(SNS)

🛠 문제

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

👩🏻‍💻 해결 방법

처음에 단순히 bfs로 풀기 위해 시도했는데 엄청난 시간초과로 인해 제대로 된 코드인지조차 확인할 수가 없었다...
그래서 다른 사람의 풀이를 참고하였고, dp를 사용해서 문제를 해결했다
우선 문제 풀이 아이디어는 현재의 노드가 얼리아답터이거나 얼리아답터가 아닐 때를 각각 계산해주는 것이었다
독립집합(얼리아답터가 아닌 노드)을 구한 후, 독립집합을 연결하는 노드가 '얼리아답터'라고 볼 수 있기 때문에, 가장 많은 독립집합을 만드는 경우를 찾은 후에 전체 노드에서 빼주면 얼리아답터의 최소 수를 구할 수 있었다

소스 코드

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

n = int(input())
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는 독립집합을 의미(내가 얼리어답터가 아닐때 dp[i][0], 얼리어답터일때 dp[i][1])
dp = [[0, 0] for _ in range(n+1)]
check = [True for _ in range(n+1)]

def dfs(cur):
  check[cur] = False  # 노드 방문 처리
  dp[cur][0] = 1 # 얼리어답터가 아닐 경우
  dp[cur][1] = 0 # 얼리어답터일 경우
  
  for i in graph[cur]:
    if check[i]:  # 자식노드이면
      dfs(i)
      dp[cur][0] += dp[i][1]
      dp[cur][1] += max(dp[i][0], dp[i][1])

dfs(1)
print(n - max(dp[1][0], dp[1][1]))