BOJ 1949 우수 마을

N개의 마을들이 트리 구조로 연결되어 있고 그곳에서 주어진 조건에 따라 우수마을을 선정할 때 우수마을 주민수의 합의 최대값을 구하는 문제이다. 주어진 조건은 다음과 같다.

1. '우수 마을'로 선정된 마을 주민 수의 합을 최대로 해야 한다.
2. '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. '우수 마을'이 아닌 마을은 적어도 하나의 '우수 마을'과 인접해 있어야 한다.

생각을 해봤는데, 루트부터 시작해서 d[i][1]=i번째 노드를 루트로 하는 서브트리에서 i번째 노드를 선택하는 경우의 최대값, d[i][0]=i번째 노드를 루트로 하는 서브트리에서 i번째 노드를 선택하지 않는 경우의 최대값으로 하려고 했는데, 문제는 i번째 노드를 선택했다면 그 노드의 child는 선택하지 않으면 되서 편한데, 문제는 선택하지 않았다면 그 child노드는 선택해도 될수도 있고 선택 안해도 될 수도 있다... 일단 시간 많이 뺏기는 것 같아서 넘어가고 강의시간에 잘 들어야겠다.

백준님의 풀이를 듣고 나니 내가 왜 이걸 생각을 못했지라는 생각이 들었다.
분명 예전에도 비슷한 문제를 풀었는데, 음 그 당시 뭔가 벽안에 갇혀있었던 것 같다.
내가 고민했던 것이 d[i][0]=i번째 노드를 루트로 하는 서브트리에서 i번재 노드를 선택하지 않는 경우의 최대값 -> 바로 이 부분에서 였는데, 선택하지 않았다면 child노드는 선택해도 될 수 있고, 안해도 될 수 있다. 근데 난 그 당시 child노드를 선택해야 되냐, 말아야 되냐에만 집착했다. 그냥 선택하는 경우와 선택하지 않는 경우 둘 중에서 최대값을 구하면 되는 것인데...!!! -> 사실 내가 진짜 고민했던 부분은 선택 안할 시에 위에서 부모의 부모에서도 선택을 안했는데 자식도 선택을 안하면 안되지 않나였던 것 같은데... 그 부분을 생각할 필요가 없는 것이... 그 경우에는 선택하지 않은 것들 중간을 그냥 선택하는 것이 더 크기 때문에.. 즉, 그렇게 하면 최대값이 될 수가 없어서 자연스레 제외된다.

그리고 백준님의 풀이를 통해 꽤 많은 사실을 깨달았다. 트리는 항상 이분 그래프라는 것부터 시작해서 다이나믹 프로그래밍의 특징, 그리고 트리를 포스트 오더로 순회, 즉 자식을 이용해서 부모를 채운다.
그런데, 이 문제의 디피의 경우 노드를 한 번씩만 방문하기 때문에 memoization이 필요없다고 하는데, 음 그것이 잘 이해가 안된다. 음 일단 코드 짜보고 이해안되면 질문해야겠다. 일단 AC를 받았다. 그리고 memoization을 안하고 하면 통과는 하는데 시간이 더 걸린다.

그리고 맞은 사람 코드 중 zlzmsrhak님의 코드를 보고 백준님이 하신 말씀을 어느정도 이해했다. 이 분의 코드를 보면 먼저 dfs를 통해 트리의 leaf node까지 내려가고, leaf node부터 선택한 경우, 선택하지 않는 경우를 다 구해놓고 위로 올라가면서 선택한 경우, 선택하지 않은 경우를 자식을 이용해서 부모를 구한다. 그리고 당연히 이렇게 하면 모든 노드를 한 번씩만 방문하면 된다. 와... 내가 한 방식은 dp가 맞긴한데, root에서부터 선택할지 안 선택할지를 결정하고 그에 따라 ...음 결국 내 방식도 지귀를 통해 일부의 leaf node를 먼저 구하게 되긴 하지만 위에서부터 보면서 memoization을 해놓은 값을 이용하고 하는데.. zlzmsrhak님의 방식은 구하고자 하는 것을 위해 필요한 것들 즉 그 노드의 아래 부분, 자식 노드들 부분을 구하면서 올라오는 방식이고, 자식노드들로 구할 수 있는 부모노드 부분은 다 구했기 때문에 더 이상 또 방문할 필요가 없고, memoization이 필요가 없다.

이제야 조금.. 포스트 오더로 방문한다는 것과 모든 노드를 한 번씩만 방문하므로 memoization이 필요없다는 말이 이해가 되는 것 같다. 정말 멋있는 문제다.

***백준님의 강의, 풀이 메모

 이 문제는 트리에서 최대 독립 집합을 구하는 문제이다.
이분 그래프면 최대 매칭으로 구할 수 있는데, 트리도 이분 그래프이다. 트리는 항상 홀수 뎁스는 짝수뎁스랑만 연결되있어서 .. 홀수랑 홀수랑 연결된 것은 존재하지 않아서.. 싸이클이 없음 그래서 항상 트리는 이분 그래프

트리의 또다른 특징은 한 노드와 연결된 간선을 보면 이 중 하나 간선은 부모로 가고 나머지는 다 자식으로 가는 간선이다. 이 특징을 이용해야 한다.

트리에서 다이나믹을 할 수 있는 이유가 트리가 사이클이 없기 때문이다. 다이나믹의 특징은 다이나믹 식을 그래프로 그렸을 때 사이클이 없다는 것이다.

d[v][1]은 쉽다. 이 마을이 선택됐다면 이 마을의 자식들은 선택이 되면 안된다.
근데 d[v][0]은 자식마을이 선택돼도 되고 안돼도 된다.
선택 되었을 때와 선택 안되었을 때 둘 중 최대값..

트리는 포스트 오더로 순회하게 된다.
모든 노드를 한번 씩만 방문하기 때문에 이 디피는 메모이제이션이 필요없다!

다이나믹을 그래프로 그려보면 DAG가 나오게 된다. 트리고 DAG이다. 부모를 이용해서 자식을 채우는 경우는 없고 자식을 이용해서 부모를 채운다.