백준 11438번 LCA 2 (C++)

https://www.acmicpc.net/problem/11438

11438번: LCA 2

 

 LCA 공부를 열심히 하고서 풀이한 문제이다. LCA는 https://tigerfrom2.tistory.com/186 여기서 자세히 설명해두었다. 이 문제는 LCA1과 같은 문제지만 주어지는 노드의 수가 늘어났고, 시간이 더 타이트해졌다. 

LCA1은 조상을 탐색할 때 1씩 올라가며 탐색해도 AC를 받을 수 있었다. 그러나 이 문제는 dp를 활용하여 LCA를 개선하는 테이블을 미리 만들어둬야 문제를 풀이할 수 있다. 

 

위 포스팅에서 자세히 다루었기 때문에 정답 코드만 쓰겠다.

 

첫 플레문제 풀이였다!

#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;

vector<int> Node[MAX];
int dep[MAX];
int dp[MAX][21];
bool visited[MAX] = { false, };

void dfs(int node, int depth) {
	visited[node] = true;
	dep[node] = depth;

	for (int i = 0; i < Node[node].size(); i++) {
		int nextNode = Node[node][i];
		if (visited[nextNode] == false) {
			dp[nextNode][0] = node;
			dfs(nextNode, depth + 1);
		}
	}
}

void setNode() {
	for (int i = 1; i < 21; i++) {
		for (int j = 1; j < MAX; j++) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
}

int LCA(int a, int b) {
	if (dep[a] < dep[b]) { // 언제나 b가 크도록
		int tmp = a;
		a = b;
		b = tmp;
	}

	for (int i = 20; i > -1; i--) {
		if (dep[b] <= dep[dp[a][i]]) a = dp[a][i];
	}

	if (a == b) return a;
	for (int i = 20; i > -1; i--) {
		if (dp[a][i] != dp[b][i]) {
			a = dp[a][i];
			b = dp[b][i];
		}
	}
	return dp[a][0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		Node[a].push_back(b);
		Node[b].push_back(a);
	}
	dep[0] = -1;
 	dfs(1, 0);
	setNode();

	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << '\n';
	}
}