BOJ 30108 - 교육적인 트리 문제

오랜만에 푼 재밌는 골드 그리디 문제였다.

쉬운 문제여서 정신적 건강에 많이 도움이 되었다.

 

문제에 정점이 N개, 루트노드가 1인 트리가 주어진다.

각 노드에는 가중치가 있고 i(1<=i<=n)개를 선택했을때 가장 큰 가중치의 합을 출력하는 문제이다.

모든 리프노드는 자신의 부모노드보다 가중치의 크기가 작거나 같기 때문에 루트노드에서 인접한 노드들을 선택하는 상황이 가장 큰 이득을 볼 수 있게 만들 수 있다. 즉, 루트노드를 우선순위큐에 넣고, 그 루트노드에 연결된 노드들을 우선순위큐에 넣으면서 계속 관리하면 각 상황마다 얻을 수 있는 가치의 크기가 최대가 된다. 

 

사실 그리디라기보다는 bfs에 가까운 문제였다.