https://www.acmicpc.net/problem/2533
트리 DP 문제
DP 테이블을 다음과 같이 정의한다.
dp[i][j] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터 인지 (j = 0) 아닌지 (j = 1) 에 따른 그 트리에서의 얼리어답터 최소 수
점화식은 다음과 같이 쓸 수 있다.
dp[i][0] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터인 경우, 모든 자식노드는 얼리어답터여도 되고, 아니어도 된다. 두 경우를 모두 구해서 최소 값을 취한다. 따라서 sum( min( dp[k][0], dp[k][1] ) ) + 1, ( k 는 직접 연결된 자식 노드들의 번호 )
dp[i][1] = i 번째 노드가 루트인 트리에 대해, 이 노드가 얼리어답터가 아닌 경우, 모든 자식 노드는 얼리어답터여야 한다.
(자신과 연결된 모든 친구가 얼리어답터여야 받아들이기 때문이다. 부모 노드는 고려하지 않아도 괜찮다. dp[i][1] 을 요구하는 경우는 부모노드가 얼리어답터인 경우에만 요구하기 때문이다.)
따라서 sum( dp[k][0] ) (이때 k는 직접 연결된 자식 노드들의 번호) 를 구한다.
초기값은 자식 노드가 없는 리프노드에 대해 결정하면 된다.
리프노드의 경우 자식이 아무도 없다면 자기 자신이 얼리어답터가 될 수 밖에 없다.
하지만 자신이 얼리어답터가 되지 않는 경우도 일단 카운팅할 수 있도록 DP 테이블에는 INF 값을 저장하였다.
얼리어답터인 부모가 자식 노드를 고려할 때는 자식 노드 중에 얼리어답터가 아닌 리프 노드를 가져오는 것이 이득이므로 이 경우만 특수하게 처리해주었다. (아래 코드에서 v2 == INF 이면 v2 = 0 으로 처리하는 부분)
import sys
from array import array
input = sys.stdin.readline
sys.setrecursionlimit(10**6+100)
INF = 987654321
YES, NO = 0, 1
def solve(node, adapter):
if dp[node][adapter] < INF:
return dp[node][adapter]
if adapter == YES:
ret = 1
for connected in graph[node]:
if visit[connected]:
continue
visit[connected] = True
v1 = solve(connected, YES)
visit[connected] = True
v2 = solve(connected, NO)
if v2 == INF:
v2 = 0
ret += min(v1, v2)
else:
ret = 0
for connected in graph[node]:
if visit[connected]:
continue
visit[connected] = True
v1 = solve(connected, YES)
ret += v1
if ret == 0:
visit[node] = False
return INF
dp[node][adapter] = ret
visit[node] = False
return ret
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
dp = [[INF, INF] for _ in range(n+1)]
visit = array('B', [False]*(n+1))
visit[1] = True
ans1 = solve(1, YES)
visit[1] = True
ans2 = solve(1, NO)
# print(dp)
print(min(ans1, ans2))
'알고리즘 (PS) > BOJ' 카테고리의 다른 글
[백준] 14442 - 벽 부수고 이동하기 2 (Java) (0) | 2024.11.07 |
---|---|
[백준] 1949 - 우수 마을 (Java) (0) | 2024.11.06 |
[백준] 2213 - 트리의 독립집합 (Python) (0) | 2024.11.05 |
[백준] 1135 - 뉴스 전하기 (Java) (0) | 2024.11.04 |
[백준] 13549 - 숨바꼭질 3 (BFS 풀이) (0) | 2024.10.01 |