백준 10075 친구 (IOI 2014 Day 2 2번)

(2023-08-29 수정 : 제 블로그 코드를 치팅하는(그대로 배껴서 내는) 경우가 너무 많아서 코드를 삭제했습니다.)

 

문제 설명(링크):

https://www.acmicpc.net/problem/10075

10075번: 친구

 

문제 요약

특이한 그래프가 주어지고, 정점마다 가중치가 있어서 최대 독립 집합을 찾아야 한다.

 

풀이

우선 그냥 최대 독립 집합을 구하는 문제는 매우 어려운 문제고, NP라 다항시간 풀이도 없다. 그러나, 트리의 경우라면 매우 쉬워진다.

 

$dp_{0, i}, dp_{1, i}$를 각각 $i$번 정점을 루트로 하는 서브트리의 최대 독립 집합의 가중치 합이라 하자. 단, $dp_{0, i}$는 $i$번 정점을 사용하지 않는 경우, 나머지 하나는 사용하는 경우라 한다. 이렇게 정의하면 상태전이도 매우 쉬운데, 정점 $v$와 그의 부모 $c$에서 $dp_{c, 1}+=dp_{v, 0}$, $dp_{c, 0}+=\max{dp_{v, 0}, dp_{v, 1}}$ 이렇게 할 수 있을 것이다.

 

주어진 그래프도 트리와 유사하다는 생각이 드는데, 트리는 한 정점을 루트로 잡으면 부모가 있고, 이 그래프도 각 정점마다(0번정점 제외) 부모의 역할을 하는 $host_v$가 있다. 따라서, 트리와 비슷하게 풀릴 것이라는 생각을 할 수 있고, 실제로도 그렇다. 여기서 핵심은, 트리의 경우를 처리할 때 $dp$들을 자식부터 확정짓는다는 사실이다.

 

$dp$식을 트리와 똑같이 정의한다. $dp_{v, 1}$을 $v$의 신뢰도로 초기화해준다. 그리고, 마지막으로 추가된 정점 $v$와 그 호스트를 $c$라 하자.

프로토콜이 0일 경우 : 프로토콜이 0이면 dp의 갱신은 트리의 경우와 일치한다.

$dp_{c, 1}+=dp_{v, 0}$

$dp_{c, 0}+=\max{dp_{v, 0}, dp_{v, 1}}$

 

프로토콜이 1일 경우 : $v$가 마지막으로 추가되었다는 것을 고려해 보면, $v$와 $c$에 연결된 정점들이 전부 동일하다는 사실을 알 수 있다. 따라서 $v$와 $c$를 동등하게 처리할 수 있다. 이는 프로토콜 2의 경우도 마찬가지이다.

 

1. $v$와 $c$가 전부 선택될 경우 : $dp_{c, 1}+=dp_{v, 1}$

2.  둘 중 하나만 선택될 경우 : $dp_{c, 1}:=\max(dp_{v, 0}+dp_{c, 1}, dp_{c, 0}+dp_{v, 1})

3.  둘 다 안 선택될 경우 : $dp_{c, 0}+=dp_{v, 0}$

 

프로토콜이 2일 경우 : 사실 프로토콜이 1일 경우와 거의 같다.

 

1. $v$와 $c$가 전부 선택될 경우는 불가능하다.

2.  둘 중 하나만 선택될 경우 : $dp_{c, 1}:=\max(dp_{v, 0}+dp_{c, 1}, dp_{c, 0}+dp_{v, 1})

3.  둘 다 안 선택될 경우 : $dp_{c, 0}+=dp_{v, 0}$

 

위 과정을 $v$를 $N-1$부터 1까지 하면 $\max(dp_{0, 0}, dp_{0, 1})$이 답이 된다.