백준 11438번 LCA 2 C++ 최소 공통 조상

리뷰

 

LCA 문제의 상위 호환버전, 노드의 개수가 2배로 많아졌고, 쿼리의 개수도 증가하였다.

시간을 좀 아껴보려고 LOG의 크기를 줄여주었더니 OutofBounds 에러가 출력되었다, LOG값을 높혀주니 AC

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

 

문제 풀이

1. n값을 입력 받고, n - 1개의 간선을 tree 벡터 배열에 양방향 간선으로 저장해 준다.
2. 루트 노드는 항상 1이기에 1부터 dfs 함수를 통해 모든 노드에 자기 자신의 깊이와 바로 윗 조상을 초기화 해준다.
3. pre_process 함수를 통해 각 노드에 변수 LOG의 값 즉 2^20개의 부모 노드를 탐색하여 저장해 준다. (메모제이션)
4. m개의 쿼리를 받고, 각 쿼리마다 두 노드의 최소 공통 조상을 lca 함수를 통해 찾아준 뒤 값을 출력해 준다.

 

참고 사항

자세한 내용은 코드 내 주석을 참고

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_N = 100001; // 노드의 최대 개수로 설정
const int LOG = 20; // 노드의 최대 개수를 log2 한 값보다 크면 됨

int n, m;
int depth[MAX_N]; // 각 노드의 깊이를 저장할 배열
int parent[MAX_N][LOG]; // 각 노드의 조상을 저장할 배열
vector<int> tree[MAX_N]; // 인접 리스트용 벡터

void dfs(int node, int par, int dep) { // 각 노드의 바로 위 조상과 자신의 깊이를 탐색
	depth[node] = dep; // 넌 dep따리 깊이다.
	parent[node][0] = par; // 너의 첫번째 부모는 par이다.
	for (int child : tree[node]) { // 인접 리스트 순회
		if (child != par) dfs(child, node, dep + 1); // 자기 자신이 부모인 경우는 패스, 아니면 재귀
	}
}

void pre_process() { // 부모의 부모를 탐색하여 저장
	for (int j = 1; j < LOG; j++) { // j는 깊이를 의미
		for (int i = 1; i <= n; i++) { // 모든 노드를 탐색
			if (parent[i][j - 1] != -1) parent[i][j] = parent[parent[i][j - 1]][j - 1]; // 현재까지 구한 깊이에서 더 아래 부모가 -1이 아니라면, 내 부모의 부모를 j깊이에 저장
		}
	}
}

int lca(int u, int v) { // 공통 부모를 찾을 귀여운 두 노드
	if (depth[u] < depth[v]) swap(u, v); // 비교를 쉽게 하기 위해 u의 depth가 항상 크게 설정

	int diff = depth[u] - depth[v]; // diff는 u와 v의 깊이 차이, 일단 깊이를 동일하게 만들어 줘야 함
	for (int i = 0; i < LOG; i++) { // diff를 LOG개(이 문제의 경우 20개)의 비트로 탐색할 것임
		if ((diff >> i) & 1) u = parent[u][i]; // i번째 비트가 존재하면 diff를 2^i만큼 줄이고, u의 깊이를 i만큼 올려줘
	}
	// 위 작업으로 인해 이제 깊이가 같아졌음
	if (u == v) return u; // v가 u의 조상일 때는 바로 리턴하면 됨

	for (int i = LOG - 1; i >= 0; i--) { // 두 노드의 최고 조상부터 탐색을 해줄 것이다.
		if (parent[u][i] != parent[v][i]) { // 만약 두 노드의 조상이 틀리다면? 깊이를 i로 변경
			u = parent[u][i];
			v = parent[v][i];
		}
	}
	// 위 작업으로 인해 현재 두 노드의 부모는 다른 상태지만 바로 위 부모는 같은 상태임 (같은 상태일 경우에는 깊이를 올려주지 않았기 때문)
	return parent[u][0]; // 바로 위 부모의 노드를 리턴 해준다.
}

int main() {
	ios::sync_with_stdio(0); // 입력 빨리 받자
	cin.tie(0); // 얘도

	cin >> n;
	for (int i = 0; i < n - 1; i++) { // 인접리스트 만들기
		int a, b; cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	// 루트부터 dfs를 돌려준다. (바로 위 조상 구하기)
	dfs(1, -1, 0); // 이 문제는 루트는 1고정이니 1부터 돌리고, 1의 부모는 -1, 1의 깊이는 0
	pre_process(); // 암케나 막돌려도 됨 이건 어차피 모든 노드 탐색할거임

	cin >> m;
	while (m--) { // 쿼리 받기
		int a, b; cin >> a >> b;
		cout << lca(a, b) << "\n"; // a와 b의 최소 공통 조상 찾고 출력
	}
}