[BOJ 1761] 정점들의 거리

풀이

BFS로 접근하였지만 노드의 개수가 최대 40000개이므로 시간초과가 발생하였다. 풀이를 찾아보니 LCA(최저 공통 조상)알고리즘을 사용하면 풀 수 있는 문제였다. LCA는 각 노드들의 2^i번째 부모 노드를 저장하고 있는 dp배열을 이용하여 시간을 계산 시간을 단축시킨다. 여기서 사용되는 점화식은 dp[i][j] = dp[dp[i][j-1]][j-1]으로 i노드의 2^j번째 부모 노드는 i노드의 2^(j-1)번째 부모노드의 2^(j-1)번째 부모노드와 같다는 것으로 해석된다. 풀이를 참조하였지만 어떻게 이런 점화식이 유도되었는지는 아직 이해가 가지 않는다.

전체 풀이 과정을 살펴보면 LCA를 위한 모든 노드의 높이를 계산해준 후 dp배열을 채워넣는다. 그리고 정점 a,b의 거리는 dist[a](루트에서 정점a의 거리) + dist[b](루트에서 정점b의 거리) - 2 * dist[lca(a,b)](루트에서 정점a와 정점b의 LCA까지 거리) 로 구해주었다.

이해가 부족한 부분

• LCA 동작 부분

int lca(int u, int v) {
	if (depth[u] > depth[v]) swap(u, v);
	// u가 무조건 부모노드
	int diff = depth[v] - depth[u];
	// 높이 차이 계산
    	// ?
	for (int i = 0; diff; i++) {
		if (diff & 1) v = dp[v][i];
		// 높이 차이가 홀수면 2^i번째 부모 노드로 이동
		diff >>= 1;
	}
	if (u == v) return u;
	for (int i = 16; i >= 0; i--) {
		if (dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
	}
	return dp[u][0];
	// 공통조상을 반환
}

• 점화식 도출 과정

for (int j = 1; j < 17; j++) {
		for (int i = 1; i <= n; i++) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

vector<pair<int, int>> adj[40001];
int n, m;
int dp[40001][17]; // dp[i][j] -> i노드의 2^j번째 부모노드
int depth[40001]; // 노드의 깊이
int dist[40001]; // 루트로부터 거리
bool visited[40001]; // 방문한 정점인지


void dfs(int cur, int d, int cost) {
	visited[cur] = true;
	// 방문한 노드 저장
	depth[cur] = d;
	// 현재 노드의 높이 저장
	dist[cur] = cost;
	// 루트에서의 거리 저장
	for (auto x : adj[cur]) {
		int next = x.first;
		// 다음 노드
		int c = x.second;
		// 다음노드까지의 거리

		if (visited[next]) continue;
		// 방문하였으면 continue
		dp[next][0] = cur;
		// 다음노드의 2^0번째 조상은 현재노드로 지정
		dfs(next, d + 1, cost + c);
		// 재귀반복
	}
}

int lca(int u, int v) {
	if (depth[u] > depth[v]) swap(u, v);
	// u가 무조건 부모노드
	int diff = depth[v] - depth[u];
	// 높이 차이 계산
	for (int i = 0; diff; i++) {
		if (diff & 1) v = dp[v][i];
		// 높이 차이가 홀수면 2^i번째 부모 노드로 이동
		diff >>= 1;
	}
	if (u == v) return u;
	for (int i = 16; i >= 0; i--) {
		if (dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
	}
	return dp[u][0];
	// 공통조상을 반환
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
	}
	dfs(1, 0, 0);
	// 노드들의 높이 계산
	for (int j = 1; j < 17; j++) {
		for (int i = 1; i <= n; i++) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cout << dist[a] + dist[b] - 2 * dist[lca(a,b)] << '\n';
	}


	return 0;
}