1949. 우수 마을

1949번: 우수 마을

---

그래프에서 독립 집합은 다음과 같이 정의된다.

그래프의 모든 정점 V의 부분집합 S에 대하여, 임의의 S의 두 정점 사이를 연결하는 간선이 없을 때 S를 독립 집합이라고 한다.
독립 집합의 크기는 정점에 가중치가 없다면 집합에 속한 정점의 개수이고, 가중치가 있다면 집합에 속한 정점의 가중치의 합이다.

따라서 이 문제는 트리(트리도 그래프이다)에서의 가장 큰 독립 집합을 구하는 문제와 같다. 마을의 주민 수가 가중치 역할을 하게 된다.

 

그런데 내가 뭔가 빠트린 것 같지 않은가?

3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

하지만 최대 독립 집합은 이 조건을 포함한다. 왜인지는 직접 생각해 보자. 사실 직관적으로는 알겠는데, 글로 쓰기가 어렵다.. 

 

 

그래서 최대 독립 집합은 어떻게 구하는가?

임의의 노드 R을 루트로 가정하자. 우리는 R을 최대 독립 집합에 포함하는 것이 나은지, 포함하지 않는 것이 나은지 계산해야 한다. 여기서 두 가지 상태를 얻을 수 있다.

0. 루트 노드를 포함하고, 루트의 자식을 포함하지 않는다

1. 루트를 포함하지 않고, 루트의 자식을 포함하거나 포함하지 않는다

나중에 값이 쓰일 수 있기 때문에 두 가지 상태를 모두 저장해야 한다. 이쯤에서 코드를 직접 작성해 보자. 어렵다면 다음을 읽어도 좋다.

R의 모든 자식 노드 child에 대해

answer[R][0] = sum(answer[child][1]) + w[R]
answer[R][1] = sum(max(answer[child][0], answer[child][1]))

을 계산하면 된다. 그래프가 무향이기 때문에 R의 루트를 중복 방문하지 않도록 처리해줘야 한다.

---

심화 문제로 2213. 트리의 독립집합이 있다. 여기서는 가장 큰 독립 집합의 원소도 찾아야 한다. 열심히 생각해 보자.