백준 2533번 사회망 서비스(SNS) - C++(cpp) 풀이

 DP 문제이다. dp(idx, isParentEarly) = 부모의 얼리어답터 여부가 isParentEarly일 때, idx번 노드를 루트로 하는 부분 트리를 완성하기 위한 얼리어답터의 수로 두고 풀었다. 부모의 얼리어답터 여부를 파라미터에 둔 이유는 이것이 자식인 idx번 노드의 얼리어답터 여부에 영향을 미치기 때문이다.

1. 부모가 얼리어답터인 경우 : idx는 얼리어답터여도 되고, 아니어도 된다. 둘 중 min값을 취하면 된다.

2. 부모가 얼리어답터가 아닌 경우 : idx번은 무조건 얼리어답터여야 한다. 부모의 인접한 노드는 모두 얼리어답터야 하기 때문에 자식인 idx는 선택권이 없다.

 

  따라서 아래와 같은 로직을 세울 수 있다.  최종적으로는 dp(루트, true)를 출력하면 된다. 루트는 부모가 없지만 얼리어답터여도 되고, 아니어도 되므로 부모가 얼리어답터인 경우랑 똑같이 취급이 가능하기 때문이다. 루트는 아무 노드나 선택하면 되고, 나는 편의상 1번을 루트로 잡아 dp(1,1)을 구했다.

int early = 1;		// 현재 노드가 얼리어답터인 경우
int noEarly = 0;	// 현재 노드가 얼리어답터가 아닌 경우
for (idx의 자식 노드들) {
	early += dp(자식, true);
  	noEarly += dp(자식, false);
}

if (부모가 얼리어답터) {
	return min(early, noEarly);
} else {
	return early;
}

 

 위에서 자식 노드들에 대해 반복문을 돌려야 하는데, 인접 노드에는 부모/자식이 섞여 있어서 이것을 판별하기 위해 시작 전 DFS를 한번 돌려서 노드 번호를 다시 매겨줬다. 이렇게 하면 항상 자식 번호가 부모보다 커지기 때문에 부모/자식 구별이 가능해진다. 바로 생각나는 대로 풀어봤는데, 좋은 풀이는 아닌 것 같다...

 

 갑자기 C++로 풀이하는 이유는 스위프트가 또 시간 초과를 내서ㅎㅎ 결국에 스위프트 시간 초과 문제도 해결하긴 했다:)