알고리즘 문제 해결 전략 2 6장 트리 (7)

24.2 문제: 등산로

등산로의 난이도는 등산로를 가다 만나는 표지판 중 최대 해발 고도와  최저 해발 고도의 차이임. 

 

24.3 풀이: 등산로

최소치를 구하는 RMQ 클래스를 재활용함.

 

24.4문제: 족보 탐험

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

 

24.5 풀이: 족보 탐험

트리의 최소 공통 조상 찾기

트리를 일렬로 펴기

트리에는 항사 n-1개의 연결이 있으므로, 2n-2번 움직이게 됨. 처음에 루트에서 시작하는 것도 경로에 포함되므로, 전체 경로의 길이는 2n-1이 됨. 

- u를 포함하는 서브트리에서 v를 포함하는 서브트리로 넘어가려면 LCA(u,v)를 거치지 않으면 안됨.

- LCAu,v)에서 그 부모 노드로 이 경로가 올라가려면 그 전에 LCA(u,v)를 루트로 하는 서비트리를 모두 돌아본 후여야 함. 따라서 LCA(u,v)의 조상 노들을 u와 v사이에 방문하는 일은 없음. 

 

특정 구간에서 최상위 노드 찾기

트리를 전위 순회하며 각 노드가 방문되는 순서대로 번호를 매기는 것임. 

 

구현하기

주어진 트리의 각 노드들의 번호를 다시 매긴 뒤, 이들의 방문 순서를 계산하고, 이 과정에서 각 노드가 출현하는 위치들을 기록해 둬야 함. 

const int MAX_N = 100000;
int n;
vector<int> child[MAX_N];
int no2serial[MAX_N], serial2no[MAX_N];
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);
}

trip[] 내에서의 두 노드의 위치를 찾고, 해당 구간의 최소치를 찾음. 이 최소치는 일련번호이기 때문에, 입력에 주어진 노드의 번호로 변환함. 그러고 나면 depth[] 배열을 이용해 거리를 계산할 수 있음. 

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];
}