백준 1949번 우수 마을 문제는 그래프 이론에서 “Maximum Independent Dominating Set” 문제의 변형입니다. 독립 집합(Independent Set)은 그래프에서 서로 인접하지 않는 정점들의 집합이고, 지배 집합(Dominating Set)은 모든 그래프의 정점이 집합에 포함되거나 집합의 원소와 인접해 있는 집합을 말합니다.
백준 1949번 우수 마을 문제에서 조건 3이 자동으로 만족되는 이유
그래프 이론적 해석
백준 1949번 문제는 트리에서의 Maximum Independent Dominating Set을 찾는 문제입니다. 우수 마을의 조건을 그래프 용어로 표현하면:
- 독립 집합(Independent Set)의 가중치 합을 최대화 (우수 마을 주민 수 합 최대화)
- 독립 집합의 정의에 따라 인접한 정점은 모두 선택될 수 없음
- 지배 집합(Dominating Set)의 조건에 따라 모든 정점은 집합에 속하거나 집합의 원소와 인접해야 함
문제 요약
백준 1949번 문제는 트리 구조의 마을에서 ‘우수 마을’을 선정하는 문제로, 다음 세 가지 조건을 만족해야 합니다:
- 우수 마을로 선정된 마을 주민 수의 총합을 최대로 해야 함
- 인접한 두 마을은 모두 우수 마을이 될 수 없음
- 우수 마을이 아닌 마을은 적어도 하나의 우수 마을과 인접해 있어야 함
DP 접근법
트리 DP를 활용하여 각 노드별로 두 가지 상태를 정의합니다:
dp[node][0]: 해당 노드가 우수 마을이 아닐 때, 서브트리의 최대 주민 수 합dp[node][1]: 해당 노드가 우수 마을일 때, 서브트리의 최대 주민 수 합
조건 3이 자동으로 만족되는 이유
중간 계산 과정에서는 dp[node][0]이 조건 3을 위반하는 상태가 계산될 수 있지만, 최종 최적해에서는 이 조건이 자동으로 만족됩니다. 이유는 다음과 같습니다:
-
비루트 노드의 경우:
dp[parent][0] += max(dp[child][0], dp[child][1])와 같은 점화식으로 계산하면서, 각 서브트리에서 조건을 만족하는 최적해를 구합니다. -
루트 노드의 경우: 최종적으로
dp[root][0]과dp[root][1]중 더 큰 값을 선택하여 최적해를 결정합니다. -
핵심 원리: 만약 어떤 노드가 우수 마을이 아니고 그 인접 노드들도 모두 우수 마을이 아니라면(조건 3 위반), 그 노드를 우수 마을로 변경하는 것이 항상 더 좋은 해가 됩니다.
계산 과정에서의 조건 위반 상태
중요한 점은 DP 배열에는 조건을 위반하는 상태값들도 계산되어 저장된다는 것입니다:
-
dp[1][0]과 같은 값은 조건 3을 위반한 상태로 계산되어 저장될 수 있습니다. 이 값이 최종 해답으로 선택되지 않더라도, 그 값 자체는 조건을 위반한 채로 DP 배열에 남아있습니다. -
마찬가지로, 어떤 중간 노드
k에 대해서도dp[k][0]이 조건 3을 위반한 상태로 계산되어 저장될 수 있습니다. 이러한 값들이 실제로 최종 최적해를 구성하는 과정에서 선택되지 않을 뿐입니다. -
DP 알고리즘은 모든 가능한 부분 문제의 해를 계산하고 저장하지만, 최종적으로는 최적의 해를 구성하는 상태들만 선택합니다. 그리고 이 문제에서는 최적의 해는 항상 세 가지 조건을 모두 만족하게 됩니다.
따라서 “조건 3은 자동으로 만족된다”라는 말은 DP 계산 과정의 모든 상태가 조건 3을 만족한다는 의미가 아니라, 최종 최적해를 구성하는 상태들은 모두 조건 3을 만족한다는 의미입니다. 이는 문제의 특성과 DP 알고리즘의 최적 부분 구조(optimal substructure) 속성 때문입니다.