BOJ 2533 사회망 서비스(SNS)

2533 사회망 서비스(SNS) [https://www.acmicpc.net/problem/2533]

문제를 읽어보시면 친구와의 관계는 Tree로 표현될 수 있다는 것을 알 수 있습니다.

이 문제는 트리 탐색과 메모리제이션을 동시에 하면서 해결 할 수 있습니다.

아래와 같은 친구관계를 가지고 있는 트리를 이용해 설명하겠습니다.

메모리제이션을 이용할 dp테이블은 다음과 같습니다

dp[i][state] : i번째 정점을 root로 가지고 있는 Subtree 에서의 최소 얼리어답터 수

    : state == 0  -> 정점 i가 얼리어답터가 아닌 경우

    : state == 1  -> 정점 i가 얼리어답터인 경우

우선 루트노드(1번 노드)부터 Leaf 노드까지 탐색합니다. 

제일 첫번째 방문하는 Leaf 노드는 5번 노드가 될 것입니다. 

5번 노드는 자식노드가 없으므로

dp[5][0] = 0 / dp[5][1] = 1 과 같이 초기화 할 수 있습니다.

방문을 마치고 다시 2번 노드로 돌아갑니다.

여기서 dp[2][0] 은 dp[5][1] 의 값을 더한 값이 됩니다.

그 이유는 2번 노드가 얼리어답터가 아닌 경우 친구는 무조건 얼리어답터가 되어야하기 때문입니다.(문제조건)

dp[2][1] 은 현재 노드가 얼리어답터 이므로 친구의 얼리어 답터의 유무가 상관없습니다. 

그러므로  dp[5][0] 과 dp[5][1] 중 작은 값을 더해주면 됩니다.

이와 같이 bottom부터 root까지 차례대로 얼리어답터 수를 갱신하면서 값을 찾으면 됩니다.

아래 주소에서 정답코드 확인가능합니다.

[https://github.com/choseungyoon/Algorithm/blob/master/2533.cpp]

설명이 잘못 되었거나 이해가 안되시는 부분 있으면 답글 달아주시면 감사드립니다!