[트리] [시도x] FAMILYTREE 족보 탐험

• FAMILYTREE

algospot.com :: FAMILYTREE

이 문제의 핵심은 '전위 탐색' 이다.

전위 탐색은 트리를 재구성하고, 부분 구간을 생성할 수 있게 해준다.

 

1. 생각.

 

이 문제를 풀기 위해서는 성벽 문제와 마찬가지로 

 

두 사람의 두 노드간의 길이를 구하는 문제이므로 최소 공통 조상을 찾아야 할 거 같다.

 

최소 공통 조상을 찾으려면 일단 트리를 구현해야한다.

 

트리를 구현한뒤 depth를 구해 각 번호마다 따로 저장해놓는다.

 

그 후 2 * lgn 만에 두 노드를 찾은후

 

거슬러 올라가면서 최소 공통 조상을 찾고

 

높이 계산을 하면 문제가 쉽게 풀릴 것 같지만

 

최악의 입력의 경우 각 수행마다 O(n)의 시간이 걸려 

 

아마 시간 초과가 나올 것이다.

 

 

2. 책에서의 풀이: LCA 최소 공통 조상

 

구간 트리는 일렬로 늘어선 배열을 처리하는 자료구조이므로, 구간 트리를 사용하기 위해 

 

주어진 입력에서 트리를 만들고 다시 트리를 쭉 '펴서' 일렬로 만들어야한다.

 

이러한 방법은 트리를 전위 순회하면서 방문하는 노드들을 순서대로 늘어놓는 것이다.

 

P = {0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 0, 6, 7, 6, 0, 8, 9, 10, 9, 11, 9, 8, 12, 8, 0}

 

전위 순회하면서 재귀 호출을 끝나고 이전 노드로 돌아오는 것도 다시 방문한 것으로 쳐서 저장해야한다.

(구간 사이에 부모노드확인용)

 

이 트리의 경로는 전체 간선을 한번 내려가고 올라가므로 2n - 2 에 처음 루트에서 시작하는 것도 경로에 포함되므로 2n -1의 길이를 가지게 된다.

 

u->v 의 경로가 방문하는 최상위 노드는 항상 최소 공통 조상(LCA)이다.

그러므로 u, v는 항상 LCA(u, v)의 서로 다른 서브트리에 포함되어 있다는 점을 이용해 다음과 같이 설명할 수 있다.

 

- u를 포함하는 서브트리에서 v를 포함하는 서브트리로 넘어가려면 LCA(u,v)는 항상 방문해야한다.

- LCA(u, v)에서 그 부모 노드로 이 경로가 올라가려면 그 전에 LCA(u,v)를 루트로 하는 서브트리를 모두 돌아본 후 이다.

  따라서 LCA(u, v)의 조상 노드들은 u , v 경로 사이에 존재하지 않는다.

 

3. 책에서의 풀이: 특정 구간에서의 최상위 노드

 

모든 노드마다 해당 노드의 깊이를 depth[]배열에 계산해두고, 두 숫자 i, j를 직접 비교하는 depth[i], depth[j]를 

서로 비교하는 구간 트리를 작성해야한다.

 

RMQ를 이용하는 방법도 있다.

상위의 노드들을 더 작은 번호를 갖도록 각 노드들의 번호를 다시 정해주는 것이다.

전위 순회하면서 각 노드가 방문되는 순서대로 번호를 매기는 것이다.

이는 각 서브트리의 루트에 가장 먼저 번호를 부여하기 때문에 자식은 항상 부모보다 작은 번호를 할당 받는다.

 

 

4. 주어진 문제 풀기

 

두사람의 번호가 주어질 때 이들의 최소 공통 조상의 번호를 O(lgn)에 찾아낼 수 있다.

 

두 사람 사이의 경로의 길이는 다음 식과 같다

 

depth[u] + depth[v]. - 2*depth[LCA(u,v)]

 

5. 책에서의 구현

 

새롭게 부여된 번호를 사용하여 

 

구간안에 최소의 번호가 그 구간의 부모가 된다.

 

전위 탐색에 의해 번호 두개가 처음 등장하는 구간 사이에는 무조건 구간사이에는 최소 공통 조상이 있다.

 

전처리 수행 시간은 O(n)에 수행되고

query() 함수는 O(lgn)만에 수행된다.

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
 
 
using namespace std;
 
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, node*2);
        int rightMin = init(array, mid + 1, right, node*2 + 1);
        return rangeMin[node] = min(leftMin, rightMin);
    }
    int query(int left, int right, int node, int nodeLeft, int nodeRight) {
        if( right < nodeLeft || nodeRight < left) return INT32_MAX;
        if( left <= nodeLeft && nodeRight <= right) 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);
    }
};
 
const int MAX_N = 100000;
int N;
vector<int> child[MAX_N];
//tree number <-> new number serial
int no2serial[MAX_N], serial2no[MAX_N];
// first visit location, 
int locInTrip[MAX_N], depth[MAX_N];
int nextSerial;
 
void traverse(int here, int d, vector<int>& trip) {
    no2serial[here] = nextSerial;
    serial2no[nextSerial] = here;
    ++nextSerial;
 
    depth[here] = d;
    locInTrip[here] = trip.size();
    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]);
    }
}
 
RMQ* prepareRMQ() {
    nextSerial = 0;
    vector<int> trip;
    traverse(0, 0, trip);
    return new RMQ(trip);
}
 
int distance(RMQ* rmq, int u, int 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];
}
 
int main() {
    int C;
    cin>>C;
    while(C--) {
        int Q;
        cin>>N>>Q;
        for(int i = 0; i < N; i++)
            child[i].clear();
        for(int i = 1; i < N; i++) {
            int a;
            cin>>a;
            child[a].push_back(i);
        }
        RMQ* rmq = prepareRMQ();
        while(Q--) {
            int a, b;
            cin>>a>>b;
            cout<<distance(rmq, a, b)<<"\n";
        }
 
    }
}

 

-알고리즘 문제해결전략 752p