✓

태그:

30. 트리에서의 동적 계획법 CLASS 6 ESSENTIAL

서브 트리의 최소 얼리어답터 수를 밑에서부터 쭉 구하면…??

풀이 비스무리한거 보기

SNS에 사람들의 관계가 트리로 주어지고 친구 관계인 모든 사람이 얼리어답터이면 아이디어를 받아들인다고 할 때, SNS에 있는 모든 사람이 아이디어를 받아들이기 위한 최소의 얼리어답터 수를 구하는 문제입니다. 알고리즘 분류를 보면 DP라고 되어있는데, 사실상 DFS로도 풀리는 것 같습니다.

루트 노드에서 시작해서 DFS를 통해 트리를 순회하는데, 현재 노드의 자식 노드로부터 두 가지 정보를 가져옵니다. 하나는 자식 노드가 얼리어답터일 때 자식 노드가 루트인 서브트리의 최소 얼리어답터 수와 자식 노드가 얼리어답터가 아닐 때의 최소 얼리어답터 수입니다. 여기서 자식 노드가 모두 얼리어답터일 때의 얼리어답터 수의 합을 구하면 현재 서브트리에서 현재 노드가 얼리어답터가 아닐 때의 최소 얼리어답터 수가 됩니다. 반대로 자식 노드가 얼리어답터일 때와 아닐 때의 작은 쪽의 합을 구하고 여기에 1을 더하면 현재 노드가 얼리어답터일 때의 최소 얼리어답터 수가 됩니다. 이 방식으로 루트에서 시작해서 DFS를 돌면 전체 트리에서의 최소 얼리어답터 수를 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-28 23:33:38

---