[BOJ] 이진 트리(13325)

[백준(BOJ)] 이진 트리(13325) C++

문제 : BOJ_13325번 이진 트리

문제 설명

트리 순회

포화이진 트리를 다루는 문제입니다.

트리의 높이 k가 주어지고, 보통의 트리 문제와는 다르게 노드의 값이 아닌 간선의 값이 주어집니다.

루트 노드에서 리프 노드로 가는 거리 중 최댓값을 x라고 한다면, 각각의 간선에 최솟값을 더하여 루트 노드에서 리프 노드까지의 각각의 모든 거리를 x를 맞춰줘야 하는 문제입니다.

---

Solution

거리를 맞출 때 상위 노드의 간선에서 값을 최댓값으로 더해줄수록 최종 거리들의 값이 줄어듭니다.

재귀의 방식을 이용했습니다.

우선 dfs를 순회하여 가장 먼 리프 노드의 거리를 구합니다

그리고 다시 리프 노드를 순회합니다.

이때, 리프 노드까지의 거리를 같게 맞추기 위해 간선에 더 해야 하는 값을 각각 부모 노드의 간선으로 다시 보내줍니다.

이진 트리이기 때문에 오른쪽과 왼쪽 값인 두 값만 들어오게 됩니다.

오른쪽과 왼쪽의 최솟값을 부모 노드의 간선에 더해주어야 마지막에 간선에 더해야 하는 값의 최솟값이 구해지므로, 왼쪽 오른쪽 간선이 필요한 값 중 최솟값을 부모 노드의 간선에 갱신해 주고, 그 간선을 다시 자신의 부모 노드의 간선에 갱신해 주는 방식으로 해결하였습니다.

---

Description

• 노드 위주가 아닌 간선 위주로 해결했습니다.
• 자신의 자식 노드의 간선 번호는 자신의 간선 번호 *2 +1, 자신의 간선 번호 *2 +2로 구할 수 있습니다.

---

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int k, edgeCnt, edgeSum;
vector<int> edge;
vector<int> minValue;
void dfs(int idx,int sum){
    if(idx*2+1<=edgeCnt) dfs(idx*2+1,sum+edge[idx*2+1]);
    if(idx*2+2<=edgeCnt) dfs(idx*2+2,sum+edge[idx*2+2]);
    edgeSum=max(edgeSum,sum);
}
int recursion(int idx,int sum){
    if(idx*2+1>edgeCnt || idx*2+2>edgeCnt) {
        return minValue[idx] = edgeSum-sum;
    }
    minValue[idx]=min(recursion(idx*2+1,(sum+edge[idx*2+1])),recursion(idx*2+2,(sum+edge[idx*2+2])));
    return minValue[idx];
}
void minFunc(int idx, int value){
    minValue[idx]-=value;
    edge[idx]+=minValue[idx];
    if(idx*2+1>edgeCnt || idx*2+2>edgeCnt) return;
    minFunc(idx*2+1,value+minValue[idx]);
    minFunc(idx*2+2,value+minValue[idx]);
}
int main(){
    cin >> k;
    for(int i =1; i<=k;i++){
        edgeCnt+=pow(2,i);
    }
    minValue.resize(edgeCnt+1);
    edge.resize(edgeCnt+1);
    for(int i=1;i<=edgeCnt;i++){
        cin >> edge[i];
    }
    dfs(1,edge[1]);
    dfs(2,edge[2]);
    recursion(1,edge[1]);
    recursion(2,edge[2]);
    minFunc(1,0);
    minFunc(2,0);
    int result=0;
    for(int i=1;i<=edgeCnt;i++) {
        result+=edge[i];
    }
    cout << result << '\n';
    return 0;
}