[algospot] FAMILYTREE

문제링크 입니다

🚀 [FAMILYTREE] 문제 😭😭😊😊😭

촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되는 것을 기본으로 합니다. 두 사람의 촌수는 이 두 사람이 부모 자식 관계를 몇 번이나 따라가야 서로 연결되는가를 나타내지요. 예를 들어 형제자매는 같은 부모를 공유하기 때문에 2촌입니다. 조부모의 자식, 즉 부모의 형제자매는 이와 같은 원리로 3촌이지요.

어떤 가문의 족보가 시조부터 시작해 쭉 주어질 때, 두 사람의 촌수를 계산하는 프로그램을 작성하세요.

🔑 [풀이]

구간트리를 이용하여 문제를 해결 합니다.
족보의 방문순서를 전위순회하여 방문하는 순서대로 나열하면 최소 공통 조상(LCA, least/lowest common ancestor)을 찾는 문제임을 알 수 있습니다.

우선 트리를 순회하여 해당 노드의 depth를 저장하고, 노드의 번호 이외에 새롭게 순회하며 새로운 번호인 serial 번호로 매기고 no2serial(노드 번호 -> 시리얼 번호), serial2no(시리얼 번호-> 노드 번호) 에 저장합니다. 또한 해당 노드를 언제 방문해 주는 지를 locInTrip에 저장합니다.
마지막으로 책에서 구현한 RMQ(구간 최소 쿼리)를 이용하여 각 구간의 최솟값을 노드로 가지는 것을 찾고 각 구간의 depth와 RMQ에서 구한 최소 값을 serial2no를 이용해 노드값으로 바꿔주고 각 구간의 거리를 계산합니다. (depth[u]+depth[v] - depth[lca])

⌨️ 입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스는 한 가문의 족보와 촌수를 계산할 사람들의 쌍들로 구성됩니다.

각 테스트 케이스의 첫 줄에는 족보에 포함된 사람의 수 N (1 <= N <= 100,000) 과 촌수를 계산할 두 사람의 수 Q (1 <= Q <= 10,000) 가 주어집니다. 이 때 족보에 포함된 사람들은 0번부터 N-1 번까지 번호가 매겨져 있으며, 0번은 항상 이 가문의 시조입니다. 테스트 케이스의 두 번째 줄에는 N-1 개의 정수로 1번부터 N-1 번까지 각 사람의 아버지의 번호가 주어집니다. 그 다음 Q 줄에 각 2개의 정수로 두 사람의 번호 a, b 가 주어집니다. (0 <= a,b < N)

족보에는 시조의 후손이 아닌 사람은 주어지지 않으며, 자기 자신의 조상이 되는 등의 모순된 입력 또한 주어지지 않습니다.

🖥 출력

각 사람의 쌍마다 한 줄에 두 사람의 촌수를 출력합니다.

🖱 입력 예제

1
13 5
0 1 1 3 3 0 6 0 8 9 9 8
2 7
10 11
4 11
7 7
10 0

💻 출력 예제

4
2
6
0
3

💎 전체 코드는 다음과 같습니다.

//
//  FAMILYTREE.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/12/27.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include "RMQ.h"
using namespace std;
ifstream fin("FAMILYTREE.txt");
const int MAXN= 100000;
vector<int> child[MAXN];
// 트리의 번호와 일련 번호 사이의 대응 관계
int no2serial[MAXN], serial2no[MAXN];
// 각 노드가 trip에 처음 등장하는 위치, 그리고 각 노드의 깊이
int locInTrip[MAXN], depth[MAXN];
// 다음 일련 번호
int nextSeiral;
const int INT_MAXN = numeric_limits<int>::max();
struct RMQ{
    int n;
    vector<int> rangeMin;
    RMQ(const vector<int>& array){
        n = array.size();
        rangeMin.resize(n*4);
        init(array,0,n-1, 1);
    }
    int init(const vector<int>& array, int left, int right, int node){
        if(left == right) return rangeMin[node] = array[left];
        int mid = (left+right)/2;
        int leftMin = init(array, left, mid, 2*node);
        int rightMin = init(array, mid+1, right, 2*node+1);
        return rangeMin[node] = min(leftMin, rightMin);
    }
    // 쿼리로 구간을 받아 그중 최솟값을 반환한다.
    int query(int left, int right, int node, int nodeLeft, int nodeRight){
        if(right < nodeLeft || left > nodeRight) return INT_MAXN;
        if(left<=nodeLeft && right>= nodeRight) return rangeMin[node];
        int mid = (nodeLeft+nodeRight)/2;
        return min(query(left, right, node*2, nodeLeft, mid), query(left,right, node*2+1,mid+1,nodeRight));
    }
    int query(int left, int right){
        return query(left,right, 1, 0, n-1);
    }
    // 트리 업데이트. 수정
    int update(int index, int newValue, int node, int nodeLeft, int nodeRight){
        if(index < nodeLeft || index > nodeRight) return rangeMin[node];
        // 리프노드까지 내려온 경우
        if(nodeLeft == nodeRight) return rangeMin[node] = newValue;
        int mid = (nodeLeft, nodeRight)/2;
        return rangeMin[node] = min(update(index, newValue, node*2, nodeLeft, mid), update(index, newValue, node*2+1, mid+1, nodeRight));
    }
    int update(int index, int newValue){
        return update(index, newValue, 1, 0, n-1);
    }
};
// 깊이가 d 인 노드 here 이하를 전위탐색한다.
void traverse(int here, int d, vector<int>& trip){
    // 위치에서 일렬 번호를 저장한다.
    no2serial[here] = nextSeiral;
    // 일렬 번호에서 위치를 저장한다.
    serial2no[nextSeiral] = here;
    // 일련 번호를 증가.
    nextSeiral++;
    // 현재 노드의 깊이 저장.
    depth[here] = d;
    // 여기가 언제 방문 했는지를 저장한다.
    locInTrip[here] = trip.size();
    // trip에 현재 노드의 일련번호를 추가한다.
    trip.push_back(no2serial[here]);
    for(int i=0; i<child[here].size(); i++){
        traverse(child[here][i], d+1, trip);
        trip.push_back(no2serial[here]);
    }
}
// u와 v사이의 거리를 계산한다.
int distance(RMQ* rmq, int u, int v){
    // trip[] 배열에서 u와 v의 첫 출현 위치를 찾는다.
    int lu = locInTrip[u], lv = locInTrip[v];
    if(lu > lv) swap(lu,lv);
    int lca = serial2no[rmq->query(lu,lv)];
    return depth[u] + depth[v] - 2*depth[lca];
}

// 트리를 순회하며 각종 필요한 정보를 계산하고,
// RMQ 구간 트리를 만들어 반환한다.
RMQ* prepareRMQ(){
    nextSeiral = 0;
    vector<int> trip;
    traverse(0,0,trip);
    return new RMQ(trip);
}

int main() {
    int test_case;
    fin >> test_case;
    for(int test=0; test<test_case; test++){
        int N, Q;
        fin >> N >> Q;
        for(int i=0; i<N; i++){
            child[i].clear();
        }
        for(int i=1; i<N; i++){
            int parent;
            fin >> parent;
            child[parent].push_back(i);
        }
        RMQ *rmq = prepareRMQ();
        for(int i=0; i<Q; i++){
            int a,b;
            fin >> a >> b;
            cout << distance(rmq,a,b) << endl;
        }
    }
}