[C/C++] 백준 - 2376 단말 정점들의 거리

www.acmicpc.net/problem/2376

2376번: 단말 정점들의 거리

- 접근법

이진 트리에서 각 단말 정점들의 거리를 가지고 트리 전체를 복원하는 문제이다.

이진 트리는 부모가 자식을 항상 2개씩(왼쪽노드,오른쪽노드)를 가지기 때문에, 단말 정점들의 거리에서 거리가 2인 경우가 항상 존재한다.

단말 정점의 거리가 2라는 것은 같은 부모(조상)을 가지고 있다는 얘기이므로, 이 두 단말 노드들을 공통된 부모(조상)으로 묶어주고 그 노드를 다시 단말노드로 본다. (단말노드로 보기 때문에 기존 단말 정점들의 거리를 수정해줘야함)

이런 작업을 재귀적으로 하다보면 ROOT까지 도달할 것이고 트리 전체가 복원이 된다.

* 감이 안잡힌다면 직접 TC를 가지고 손으로 해보는것을 추천한다.

 

트리를 복원한다면 단말 정점들 사이의 거리를 구하는 것은 어렵지 않을것이다. (이 문제에서는 단말 정점 개수가 최대 1000개이므로 따로 최적화된 LCA알고리즘을 써서 계산할 필요는 없다)

 

---

- 소스코드

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int, int> trees;
unordered_map<int, int> parents;
int N;
int tree_node;
int from, to;
vector<vector<int> > edge;
void make_tree() {
    int left_node, right_node;
    tree_node = N+1;
    while (!edge.empty()) {
        for (int i = 0; i < edge.size(); i++) {
            left_node = edge[i][0];
            right_node = edge[i][1];
            if (edge[i][2] == 2) {
                trees[left_node] = tree_node;
                trees[right_node] = tree_node;
                if (i - 1 >= 0) {
                    edge[i - 1][1] = tree_node;
                    edge[i - 1][2]--;
                }
                if (i + 1 < edge.size()) {
                    edge[i + 1][0] = tree_node;
                    edge[i + 1][2]--;
                }
                edge.erase(edge.begin() + i);
                tree_node++;
            }
        }
    }
}
int find_parents(int x, int y) {
    int depth = 1;
    while (x != 0) {
        x = trees[x];
        parents[x] = depth++;
    }
    depth = 1;
    while (y != 0) {
        y = trees[y];
        depth++;
        if (parents[y] != 0) {
            break;
        }
    }
    return (parents[y] + depth-1);
}
int main() {
    int a;
    cin >> N;
    for (int i = 1; i <=N-1; i++) {
        cin >> a;
        edge.push_back({ i,i + 1,a });
    }
    cin >> from >> to;
    make_tree();
    printf("%d", find_parents(from, to));
    return 0;
}