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

 

문제

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

 

 

난이도

골드 3

 

 

 

코드

import sys
sys.setrecursionlimit(10**6)

def find(node) : 
    for neighbor in friend[node] :
        if not visit[neighbor] :
            visit[neighbor] = True
            find(neighbor)
            dp[node][1] += min(dp[neighbor])
            dp[node][0] += dp[neighbor][1]

N = int(sys.stdin.readline())
friend = [[] for _ in range(N+1)]
for _ in range(N-1) :
    u,v = map(int,sys.stdin.readline().split())
    friend[u].append(v)
    friend[v].append(u)
dp = [[0,1] for _ in range(N+1)]
visit = [False] * (N+1)
visit[1] = True
find(1)
print(min(dp[1]))

 

 

 

풀이

트리에서의 다이나믹 프로그래밍 문제이다.

하나의 노드는 얼리어답터일 때와 그렇지 않을 때로 구분될 수 있다.

dp[node][0] = 얼리어답터가 아닐 때, 자식의 얼리어답터 최소 수

dp[node][1] = 얼리어답터일 때, 자신과 자식의 얼리어답터 최소 수

이렇게 해서 자식노드부터 dp를 채워나가 계산하였다.

 

나는 1번 노드부터 방문하여 자식노드들부터 dp를 계산하여 올라오게 하였다.

꼭 1번 노드부터 하지않아도 상관없다.

대신 정답을 출력할 때 시작 노드의 dp값 중 최솟값을 출력해야한다.

 

트리에서의 DP는 경험이 부족해서 처음 생각할 때 헤맸다.

생각만 한다면 구현은 어렵지 않았다.