[BOJ, C++]#13325_이진 트리, 이진 트리, 포화 이진 트리, DFS, 재귀 DFS

#1. 문제

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

 

---

 

#2. 풀이

 

1. 이진트리

[자료구조]#5_트리

이진트리는 트리 자료구조의 한 종류로, 각 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하인 트리 자료구조입니다. 따라서, 이진트리의 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가지며, 부모-자식 관계가 하위 레벨에서도 순환적으로 반복되는 계층 구조를 형성해, 전체 트리의 각 서브트리도 모두 이진트리가 됩니다.

 

2. DFS

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 노드로부터 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색을 합니다. 일반적으로, DFS는 재구 호출 혹은 스택 자료구조를 활용해 구현합니다.

 

3. 현재 정점 기준 왼쪽 서브트리의 최단 경로와 오른쪽 서브트리의 최단 경로 비교

1. 먼저, 힙 구현에 활용되는 배열 인덱싱 방법(부모 = 2/i, 왼쪽 자식 = 2*i, 오른쪽 자식 = 2*i+1)을 고려하여, 배열에 각 간선의 가중치를 저장합니다.
2. 재귀 호출 DFS를 구현합니다.
3. 먼저, 종료 조건은 현재 노드가 자식 노드가 없는 단말 노드일 경우 탐색을 종료하고, 간선의 가중치를 결과 값에 더한 뒤 그 값을 반환합니다.
4. 다음으로, 왼쪽 자식 노드와 오른쪽 자식 노드에 대한 재귀호출, 중복 계산을 방지하기 위해 두 결과 값을 뺀 절댓값에 현재 노드의 가중치 값을 더해 결과 값에 더해줍니다.
5. 마지막으로, 현재 노드의 가중치 값 + 왼쪽 혹은 오른쪽 자식 노드의 결과 값 중 최대가 되는 값(최대 경로 값을 갖는 경로)을 더해주고, 이를 반환해 줍니다. 
6. 말이 조금 복잡하지만, 현재 노드의 자식 노드(왼쪽/. 오른쪽) 중 그 경로 값이 최대가 되는 값을 결과 값으로 반환해 주는 동시에, 중복 계산을 방지하기 위해 왼쪽과 오른쪽 경로의 경로 값을 빼주어 현재 간선의 가중치에 더해주고 이를 결과 값에 반영해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/13325
*   @문제: 가중치 포화 이진 트리에서 루트로부터 모든 리프 노드의 경로에서 에지들의 가중치 증가를 통해 모든 경로의 거리 값을 최소 값으로 통일.
*   @설명
        1. 높이 n, 노드 갯수 2^(n+1) - 1개, 리프 노드 갯수 2ⁿ개
        2. 부모 = i/2, 왼쪽 2*i. 오른쪽 2*i+1
        3. 현재 노드를 시작으로 왼쪽/오른쪽 자식 노드를 통하는 경로의 최대 경로는 곧 최대 값을 갖는 어느 한 경로입니다.
        현재 노드를 기점으로 왼쪽 서브트리의 총 경로 값이 아닙니다!
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int K, ans;
vector<int> tree;

int dfs(int cur, const int& size)
{
    //@리프 노드
    if(cur*2 >= size)
    {
        ans+= tree[cur];
        return tree[cur];
    }

    //@왼쪽 자식 노드
    int leftChild = dfs(2*cur, size);
    //@오른쪽 자식 노드
    int rightChild = dfs(2*cur+1, size);

    //@현재 가중치 + 두 경로 중 '최대 값'으로 업데이트 된 경로의 증가된 값
    ans += tree[cur] + abs(leftChild-rightChild);

    return tree[cur] + max(leftChild, rightChild);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> K;

    //@총 노드 개수, 2^(K+1)-1
    int n = (1<<(K+1)) -1;
    tree.resize(n+1, 0);

    for(int i=2; i<=n; ++i)
    {
        cin >> tree[i];
    }

    //@DFS 수행
    dfs(1, n);

    cout << ans;

    return 0;
}

 

---