[2533] 사회망 서비스(SNS)

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

2533번: 사회망 서비스(SNS)

동적 계획법 문제다.

 

풀이

동적 계획법을 기본으로 그래프탐색을 통해 접근해야 한다. 부모 노드가 얼리어답터라면 자식노드는 얼리어답터 여부와 상관없이 해당 부분의 부모와 자식에게는 아이디어 전파가 가능하다. 반대로 부모가 얼리어답터가 아니라면 자식은 반드시 얼리어답터 이어야 한다. 

 

두 개의 자식을 가진 부모노드가 얼리어답터가 경우 아이디어가 전파되려면 그림과 같은 4개의 경우의 수가 만들어진다. 해당 부분에서의 정답은 가장 첫 번째의 경우가 최소조건임을 알 수 있다. 

 

하지만 반대로 부모가 얼리어답터가 아닐 경우, 자식들은 모두 얼리어답터 이어야만 조건이 맞다. 즉 우리는 부모노드가 얼리어답터인지, 일반인인지의 경우를 따져 얼리어답터의 수를 계산할 수 있게 된다.

 

그래프는 다음과 같이 두 개의 값을 가지는 형태로 구현한다. 0번 인덱스에는 자신이 일반인일 경우 얼리어답터의 수, 1번 인덱스에는 자신이 얼리어답터일 경우 얼리어답터의 수. 처음에는 당연히 자기 자신만 얼리어답터인 경우로 1로 초기화되어 있다.

 

먼저 부모가 얼리어답터가 아닐 경우부터 살펴본다. 해당경우는 자식노드가 무조건 얼리어답터이어야 하기 때문에 자식의 수만큼 더해진 값이 얼리어답터의 최소 개수다.

 

하지만 부모가 얼리어답터인 경우, 자식이 얼리어답터의 여부와 상관없이 최솟값을 가져오면 조건이 성립된다.

 

parent[0] += child_0[1] + child_1[1]...child_N[1]
parent[1] += min(child_0[0],child_0[1]) + ... min(child_N[0],child_N[1]))

 

즉 모든 노드가 [0,1] 형태로 초기화되어있을 경우, 해당 점화식을 사용하여 리프 노드의 정보를 통해 루트 노드까지 최소 얼리어답터의 수를 구할 수 있게 된다.

 

예제의 경우 다음과 같은 형태로 결과가 나오며, 출력은 루트노드의 두 개의 값 중 최솟값을 출력하면 된다. 코드로 보는 것이 이해하기 더 쉽다.

 

정답 코드