[SWEA] 4534. 트리 흑백 색칠

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

아무리봐도 완전탐색으로 풀수없는 문제라고 생각했다

일단, 완전탐색을 하게될 경우 시간복잡도는 자식노드들에 따라 기하급수적으로 늘어나는데, 예를들어

가장큰 부모노드에서, 자식노드까지 가는 모든 경우의 수를 다 탐색하는 상황을 생각해보면,

노드를 내려갈때마다 전부탐색해야하는 굉장히 복잡한상황이 나오면서, 트리이기 때문에 그러한 방향성 역시

일정하지 않다는 문제점이 존재한다.

 

그래서, Dynamic Programming 을 생각했고, 처음에 생각한것은

Dp[index][0], Dp[index][1] 로, 0이 검은색, 1이 흰색이라 가정했을때,

부모노드가 자식노드에 색에 의해 결정되는 식을 세워보면,

Dp[Parent][0] = Dp[Parent][0] * Dp[child][1] 이 된다. 처음에는, 잘못하고 + 로 놨는데, 경우의 수 이므로, *이 맞다.

또한, 부모가 검은색을 취하기 위해서는 문제 조건에의거해서 자식은 무조건, 흰색 이여 야만 하며

위의 식처럼 쓸수있게 된다.

두번째로, 부모가 흰색일 경우는 자식이 흰색을 쓰든 검은색을 쓰든 상관치 않는다.

Dp[Parent][1] = Dp[Parent][1] * (Sum(Dp[Child][0] + Dp[child][1]))과 같이, 자식들의 모든 경우의 수를 더한것을 곱해나가는 방식으로 수식을 전개할수있다.

 

또한, 문제를 풀면서 제일 난감했던것은 트리의 구조가 아닐까 싶다.

부모를 찾아가는 과정이 필요할거같은데,  이것은 생각보다 시간복잡도가 클것이라생각했다.(최대 10만개)

이를 해결하기 위해, 입력을 받으면서 부모를 정해주고, 최대 부모에 대한 정보를 getParent()함수를 통해

찾아내서, 그 부모에서 자식까지 가는 범위를 정한뒤, DP를 전개해 정답을 얻을수 있었다.