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

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

 

❗풀이방법

• 트리 기반 dp로 문제 풀이
• 루트 노드인 정점 1에서 dfs 시작
• 자식 노드부터 값을 계산하여 부모로 거슬러 오는 구조
• 2가지 케이스
  • 부모 x, 자식 o
  • 부모 o, 자식 x or 자식 o

 

❗코드

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

n = int(input())

graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

dp = [[0, 0] for _ in range(n+1)]
# 얼리어댑터가 아닐 때0, 맞을 때1



for _ in range(n-1):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    visited[v] = 1

    dp[v][0] = 0
    dp[v][1] = 1


    for i in graph[v]:
        if not visited[i]:
			# 자식 노드의 값을 먼저 계산해야 부모 노드 계산 가능
            dfs(i)

            # v: 부모, i: 자식
            # 자식을 기반으로 부모의 값을 지정해줌
            dp[v][0] += dp[i][1]
            dp[v][1] += min(dp[i][0], dp[i][1])


# 정점 1에서 시작
dfs(1)

# 트리 기반 dp이기 때문에 루트노드에서 값을 구함
print(min(dp[1][0], dp[1][1]))