Page 28 -

가중 최대 안정 집합 문제

각 꼭짓점 v ∈ V에 가중치 w(v)가 부여된 트리 G = (V, E)가 주어졌을 때(특히 루트가 지
정되지 않은 트리) 트리 G의 다양한 안정 집합 중에서 안정 집합에 포함된 꼭짓점 가중치 총
합의 최댓값을 구하라.

여기서 13.10절에서 설명한 걸 다시 떠올려 보길 바랍니다. 루트가 없는 트리라도 편의상 적당히
하나를 골라 루트 트리로 바꿔서 보기 편하게 만들고 문제를 푸는 방법을 봤습니다. 가중 안정 집
합 문제가 바로 그런 문제입니다. 루트를 하나 정해서 루트 트리로 만들고, 트리에서 동적 계획법

으로 최적해를 구합니다(그림 18-2). 가중 최대 안정 집합 문제에서는 부분 문제를 다음과 같이
정의합니다.

그림 18-2 트리에서 동적 계획법의 사고법

vܳ ܖ౟۽ ೞח ࠗ࠙ ౟ܻী
ҙೠ ޙઁܳ ࠗ࠙ ޙઁ۽ ೞח
ز੸ ҅ദߨ

v

가중 최대 안정 집합 문제에 대한 트리의 동적 계획법

● dp1[v] ← 꼭짓점 v를 루트로 하는 부분 트리 안에서 안정 집합 가중치의 최댓값(꼭짓
점 v를 선택하지 않은 경우)
● dp2[v] ← 꼭짓점 v를 루트로 하는 부분 트리 안에서 안정 집합 가중치의 최댓값(꼭짓
점 v를 선택한 경우)

그리고 각 꼭짓점 v에 대해 자식 꼭짓점 c를 루트로 하는 부분 트리에 관한 정보를 모읍니다.

dp1에 대해

v의 각 자식 꼭짓점 c를 루트로 하는 각 부분 트리에 대한 최대 가중치의 총합을 구하면 되므로

384