[일반] 백준 18638 (D5, The Older We Are) 풀이!

[익명(58.228)]

안뇽하세요 저번에 작성한 풀이가 개추를 와바박 먹엇길래 한번 더 올려보아요,,, 이 문제도 정말 재밌게 풀었는데 많이 풀리진 않아 작성해보아요

문제 설명:

각 정점에 가중치가 있는 트리가 주어진다. 이 트리에서 임의의 루트를 잡아 임의의 DFS 탐색을 진행하는데, 탐색의 점수는 모든 i {1<=i<=N}에 대해 i * (i번째로 방문한 정점의 가중치)의 합으로 계산된다. 점수를 최소화했을때 그 점수를 구하시오.

https://www.acmicpc.net/problem/18638

Baekjoon Online Judge

(스포 방지)

(평균iq200+개고수피에쓰갤러리이용자분들은한번고민해보시고내려주세용ㅎㅎ)

문제 풀이:

우선 한 임의의 루트를 잡고 풀어봅시다.

각 자식 노드당 그 노드의 서브트리에 해당하는 최적해의 점수, 서브트리에 속하는 정점 수, 서브트리에 속하는 가중치의 합을 벌써 알고 있다고 가정합시다. 이 정보를 가지고 현재 노드의 최적해의 점수를 계산하는게 가능할까요?

조금 더 쉽게 생각하기 위해, 자식 노드의 수가 두개라고 가정합시다. A와 B로 부르겠습니다. 그럼 A->B 순으로 방문하는 순회와 B->A 순으로 방문하는 순회의 점수는 어떻게 다를까요?

SUM[i]를 i번 노드의 가중치의 합, DP[i]를 i번의 노드의 서브트리를 최적으로 순회했을때의 점수, CNT[i]를 i번 노드의 서브트리에 속하는 정점 수로 정의하겠습니다.

A->B로 방문한다면:

현재 노드 방문 = 1 X 현재 노드의 가중치

A의 서브트리를 최적해에 따라 순회 = 미리 계산해둔 값 + 1 X A의 서브트리의 가중치의 합 (계산해둔 값은 순회를 A에서 시작한다고 가정했지만, 이번엔 A가 두 번째로 방문됐으니 가중치가 각각 한번 더 점수에 더해짐)

B의 서브트리를 최적해에 따라 순회 = 미리 계산해둔 값 + (1 + A의 서브트리의 노드의 수) X B의 서브트리의 가중치의 합 (비슷한 원리로 이번엔 B가 (1 + A의 서브트리의 노드의 수)번째로 방문됨)

최종합 = DP[A]+DP[B]+SUM[A]+(CNT[A]+1)SUM[B]

B->A로 방문한다면:

현재 노드 방문 = 1 X 현재 노드의 가중치

B의 서브트리를 최적해에 따라 순회 = 미리 계산해둔 값 + 1 X B의 서브트리의 가중치의 합

A의 서브트리를 최적해에 따라 순회 = 미리 계산해둔 값 + (1 + B의 서브트리의 노드의 수) X A의 서브트리의 가중치의 합

최종합 = DP[A]+DP[B]+SUM[B]+(CNT[B]+1)SUM[A]

겠죠. 따라서, 이 중 더 작은 값을 고르는게 최적이겠죠.

이제 두 자식 노드를 비교했을때 어느 노드를 순회하는게 더 최적인지 판별하는 법을 찾았으니, Exchange-based sorting을 진행하여 임의의 갯수의 자식 노드들을 순회하는 최적의 순서도 찾을 수 있습니다. 자식 노드들의 최적해, 가중치의 합, 정점들의 수 등의 정보가 필요하니 DFS로 트리를 순회하면서 Tree DP를 진행하면 됩니다.

다음과 같은 방식으로 한 루트에 대해 최적해를 찾을 수 있습니다. 이 풀이도 쉬운건 아니지만 (최소 플3) 이 문제는 모든 루트에 대해 최적해를 찾는걸 요구하고 있죠. 여기까지 풀이를 도출한 뒤 대충 뭘 해야지 풀 수 있는지는 파악했지만 제가 딱 싫어하는 유형이기에 던질까 진심으로 고민했습니다.

rerooting Tree DP라는 기법을 사용할 것입니다. 사실 기법이라고 하기엔 거창합니다. 개념이 확 와닿는 이미지 하나를 첨부하겠습니다.

이런 식으로 어떠한 노드를 루트로 바꾸고 싶으면 순회상 부모 노드와 그 위로 있는 모든 정점들을 서브트리로 취급하면서 아까와 동일한 풀이를 적용하면 됩니다. 다만, 위에 있는 정점들을 서브트리화 시키는 과정이 까다롭습니다. 아까 풀이에서 서브트리에 필요한 값이 노드의 수, 가중치의 합, 그리고 최적해의 점수였죠? 처음 두 값은 어렵지 않게 구할 수 있지만, 마지막 최적해를 적당히 구해야 하는데, 이 부분이 직관적으로 떠오르진 않습니다. Rerooting DP를 제가 싫어하는 이유도 이 때문인데, 이렇게 거꾸로 돌려서 값을 계산하는 방법은 문제마다 달라서 그때그때 생각해줘야 합니다. 이 문제의 경우는 DFS를 하며 어떠한 노드를 루트로 삼아 부모 노드를 서브트리화 시킨 후 자식 노드들로 내려갈땐 그 자식 노드의 서브트리만 제외하고 최적해를 구한 다음 자식 노드에게 그 최적해의 값을 전달하는 방식으로 해결할 수 있습니다. 이 설명이 약간 애매모호한데, 코드를 보면서 이해해주시면 감사하겟습니당

코드:

http://boj.kr/97f307c55cd44dcb9be40fe2a1959918

Baekjoon Online Judge

끗!!! 풀이를 작성하는게 복습에도 좋고 재미도 잇네요 괜찮으시다면 앞으로도 종종 올리겟습니다