Algospot FAMILYTREE

문제 링크입니다: https://algospot.com/judge/problem/read/FAMILYTREE

구간 트리(Segment Tree) 문제이기 때문에 Algospot MORDOR(http://jaimemin.tistory.com/662) 문제처럼 RMQ(Range Minimum Query) 구조체를 이용해서 푸는 문제였습니다.

두 노드의 촌수 계산을 위해서는 공통 조상 LCA(Least Common Ancestor)를 찾는 것이 핵심입니다.

예를 들어 u와 v의 촌 수를 계산하기 위해서는 (u의 깊이와 + v의 깊이 - 2 * LCA(u, v)의 깊이)를 구하면 됩니다!

새그먼트 트리는 일렬로 늘어선 배열을 처리하는 자료구조이기 때문에 해당 알고리즘을 사용하기 위해서는 트리를 펴서 일렬로 만들어야 합니다.

이렬로 피기 위해서는 자료구조 시간에 많이 다루어본 전위 순회(Preorder Traversal)을 이용합니다.

주의할 점은, 자료구조처럼 노드를 한 번씩만 출력하는 것이 아니라 경로 전체 즉, 한 노드가 여러번 출력되도록 해야 합니다.

앞서 u와 v의 촌 수를 계산하기 위해서는 깊이를 알아야한다고 했기 떄문에 depth[] 배열을 이용하여 해당 노드의 깊이를 저장하면 distance 함수를 보다 수월하게 구현할 수 있습니다!

*전위 순회를 통해 각 노드에 새로 붙인 번호를 일렬 번호(serial number)라고 부릅니다. 따라서 각 노드와 일렬번호의 관계를 파악하기 위해 no2serial[], serial2no[] 배열을 사용합니다.

*전위 순회를 할 때 경로 전체를 출력하기 때문에 해당 노드가 제일 먼저 출력했을 때의 위치를 locInTrip[] 배열에 저장합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAXN = 100000;

const int MAX = 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);

        }

        //node 노드가 array[left...right] 배열을 표현할 때

        //node를 루트로 하는 서브트리를 초기화하고, 이 구간의 최소치를 반환한다

        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);

        }

        //node가 표현하는 범위 array[nodeLeft..nodeRight]가 주어질 때

        //이 범위와 array[left..right]의 교집합의 최소치를 구한다

        int query(int left, int right, int node, int nodeLeft, int nodeRight)

        {

                 //두 구간이 겹치지 않으면 아주 큰 값을 반환한다: 무시 됨

                 if (right < nodeLeft || nodeRight < left)

                         return MAX;

                 //node가 표현하는 범위가 array[left..right]에 완전히 포함되는 경우

                 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));

        }

        //query()를 외부에서 호출하기 위한 인터페이스

        int query(int left, int right)

        {

                 return query(left, right, 1, 0, n - 1);

        }

        //array[index]=newValue로 바뀌었을 떄 node를 루트로 하는

        //구간 트리를 갱신하고 노드가 표현하는 구간의 최소치를 반환한다

        int update(int index, int newValue, int node, int nodeLeft, int nodeRight)

        {

                 //index가 노드가 표현하는 구간과 상관없는 경우엔 무시한다

                 if (index < nodeLeft || nodeRight < index)

                         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));

        }

        //update()를 외부에서 호출하기 위한 인터페이스

        int update(int index, int newValue)

        {

                 return update(index, newValue, 1, 0, n - 1);

        }

};

 

int N;

vector<int> child[MAXN];

//트리의 번호와 일렬 번호 사이의 대응 관계

int no2serial[MAXN], serial2no[MAXN];

//각 노드가 trip에 처음 등장하는 위치, 그리고 각 노드의 깊이

int locInTrip[MAXN], depth[MAXN];

//다음 일렬번호

int nextSerial;

 

//깊이가 d인 노드 here 이하를 전위 탐색(preorder Traversal)

void traverse(int here, int d, vector<int> &trip)

{

        //traverse()가 처음 방문하자마자 일렬 번호를 부여

        //이렇게 하면 항상 부모는 자손보다 작은 일렬 번호를 갖게 된다

        no2serial[here] = nextSerial;

        serial2no[nextSerial] = here;

        ++nextSerial;

        //깊이 계산

        depth[here] = d;

        //trip에 현재 노드의 일렬 번호를 추가

        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 구간 트리를 만들어 반환

RMQ *prepareRMQ(void)

{

        nextSerial = 0;

        //순회 과정에서 만나는 노드들의 일렬 번호를 담는다

        vector<int> trip;

        traverse(0, 0, trip);

        return new RMQ(trip);

}

 

//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);

        //rmq는 u와 v의 최소 공통 조상의 일렬번호를 반환

        int lca = serial2no[rmq->query(lu, lv)]; //least common ancestor

        return depth[u] + depth[v] - 2 * depth[lca];

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 for (int j = 0; j < MAXN; j++)

                         child[j].clear();

 

                 int N, Q; //족보에 포함된 사람의 수, 촌수를 계산할 두 사람의 수

                 cin >> N >> Q;

 

                 for (int j = 1; j < N; j++)

                 {

                         int parent;

                         cin >> parent;

 

                         child[parent].push_back(j);

                 }

 

                 nextSerial = 0;

                 RMQ *pRmq = prepareRMQ();

 

                 for (int j = 0; j < Q; j++)

                 {

                         int a, b;

                         cin >> a >> b;

 

                         cout << distance(pRmq, a, b) << endl;

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]