Baekjoon-2533-사회망 서비스(SNS)
04 Oct 2022Leaf 만 정답을 가지고 있다고 생각해서 그 조건을 넣으려 했는데, DFS와 DP를 사용하면 그럴 필요가 없다. 어차피 부모 노드를 거쳐서 온 것이므로 다시 올라갈 염려는 없기 때문이다.
그리고 점화식을 세워보면 간단히 풀린다!
그리고 예상과 같이 이런 반례에서 문제가 생길 수 있는데, 잘 처리해주면 된다.
3
1 2
2 3
(정답) 1
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
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 = [[0,1] for _ in range(N+1)] # initialize by leaf
visited = [0 for _ in range(N+1)]
# dp[i][1]: i가 얼리어답터일 때 최적해
# dp[i][0]: i가 얼리어답터가 아닐 때 최적해
def dfs(u):
visited[u] = 1
for v in graph[u]:
if visited[v] == 0:
dfs(v)
dp[u][0] += dp[v][1] # u가 얼리어답터가 아닐 때 -> v는 전부 얼리어답터
dp[u][1] += min(dp[v]) # u가 얼리어답터일 때 -> v는 상관 없음
dfs(1)
print(min(dp[1]))