[코딩테스트 준비] 골드 1문제 - 1949 우수 마을

1949 우수 마을

트리 DP를 이용한 최대 가중 독립집합 with 지배 조건

 

1. 문제 해석

문제는 트리 구조의 그래프에서 일부 정점을 선택하여 다음 조건을 만족하는 부분집합을 찾는 것이다.

1. 선택된 마을의 주민 수 합을 최대화해야 한다.
2. 인접한 두 마을은 동시에 선택할 수 없다.
   → 독립집합(Independent Set) 조건
3. 선택되지 않은 모든 마을은 적어도 하나의 선택된 마을과 인접해야 한다.
   → 지배(Dominating) 조건

즉, 본 문제는
트리에서 지배 조건을 만족하는 최대 가중 독립집합을 구하는 문제로 해석할 수 있다.

 

2. 접근 방법 개요

트리는 사이클이 없으므로, 임의의 노드를 루트로 잡아 DFS를 수행하며
서브트리 단위로 최적해를 계산하는 트리 DP 방식이 적합하다.

각 노드에 대해 “선택하는 경우”와 “선택하지 않는 경우”를 분리하여 고려한다.

 

3. DP 상태 정의

루트를 기준으로 트리를 구성하고, 각 노드 u에 대해 다음과 같이 정의한다.

• dp[u][1] : 마을 u를 우수 마을로 선택했을 때
  u를 루트로 하는 서브트리에서 얻을 수 있는 최대 주민 수
• dp[u][0] : 마을 u를 선택하지 않았을 때
  u를 루트로 하는 서브트리에서 얻을 수 있는 최대 주민 수

 

4. 점화식

4.1 현재 마을을 선택한 경우 (dp[u][1])

• 인접한 마을은 선택할 수 없으므로, 모든 자식은 반드시 선택되지 않아야 한다.
• 자식이 선택되지 않은 경우라도, 현재 마을 u가 지배 조건을 만족시켜 준다.

따라서 다음과 같이 계산된다.

 

dp[u][1] = population[u] + Σ dp[v][0] (v는 u의 자식)

 

4.2 현재 마을을 선택하지 않은 경우 (dp[u][0])

이 경우가 문제의 핵심이다.

• u가 선택되지 않았으므로,
  u는 반드시 인접한 마을 중 하나에 의해 지배되어야 한다.
• DFS 기준에서는 부모의 선택 여부를 알 수 없으므로,
  자식 중 최소 하나는 반드시 선택되어야 한다.

자식 v에 대해 선택지는 두 가지다.

• v를 선택 → dp[v][1]
• v를 선택하지 않음 → dp[v][0]

기본적으로는 각 자식에 대해 max(dp[v][0], dp[v][1])를 선택하되,
모든 자식이 선택되지 않는 상황이 발생하면,
손해가 가장 적은 자식 하나를 강제로 선택해야 한다.

이를 위해 다음 절차를 사용한다.

1. 각 자식에 대해 더 큰 값을 선택하며 합을 계산
2. 선택된 자식이 하나도 없다면
   dp[v][1] - dp[v][0] 값이 가장 작은 자식을 선택

 

5. 루트 처리 및 최종 결과

루트 노드는 부모가 없으므로,
루트가 선택되지 않았을 경우에도 자식 중 하나가 반드시 선택되어야 한다.

이는 dp[u][0] 계산 과정에서 이미 보장되므로,
최종 결과는 다음 중 최댓값이다.

 

정리

이 문제는 단순한 최대 독립집합 문제가 아니라,
선택되지 않은 정점도 반드시 커버해야 한다는 지배 조건이 추가된 문제이다.

트리 구조라는 점을 이용해
DFS 기반 트리 DP로 상태를 분리하고,
“최소 하나의 자식 선택” 조건을 정확히 처리하는 것이 핵심이다.