[백준 02533] 사회망 서비스(SNS) [Java]

문제

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

---

풀이

우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.

그래프를 구성 후 dfs를 진행하자.

 

얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.

맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.

하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.

여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.

dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수

dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.

리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 상태에 대해 갱신해주자.

부모 노드가 얼리 어답터인 경우 자식 노드가 얼리 어답터거나 아닌 경우 중 최소값을 더해주자.

트리의 구성에 따라 부모-자식이 둘 다 얼리 어답터인 경우가 최소일 수 있기 때문이다.

부모 노드가 얼리 어답터가 아닌 경우, 자식 노드가 얼리 어답터인 경우를 더해주자.

이 과정을 반복하며 dfs를 끝내고 루트 노드가 얼리 어답터인 경우와 아닌 경우 중 최소값을 출력하면 된다.

---

소스코드

보기