[백준 11438] LCA2 (C++)

문제 출처 : https://www.acmicpc.net/problem/11438

11438번: LCA 2

트리를 만들고 깊이를 체크해준다.

이후 깊이에 맞게 부모를 설정해준다.

같은 깊이까지 끌어올리고 두 수가 같은지 비교후 같다면 출력, 다르다면 한단계 올라가기가 생각 한 풀이방법이다.

 

#define MAX_NODE 100001
#define MAX_DEPTH 17 // 2^17 > 100000
int parent[MAX_NODE][MAX_DEPTH];
int depth[MAX_NODE];
bool check[MAX_NODE];
vector<int> tree[MAX_NODE];

MAX_NODE는 문제에서 주어진 정점의 최대 개수를, MAX_DEPTH는 log2(100001) 약 16.6이므로 17을 설정해 주었다.

부모를 담을 배열과 깊이를 담을 배열, dfs에서 체크를 해줄 배열, 트리틑 만들 tree벡터를 선언해주었다.

 

int n, m;
cin >> n;
for (int i = 1; i < n; i++) {
	int u, v;
	cin >> u >> v;
	tree[u].push_back(v);
	tree[v].push_back(u);
}
DFS(1, 0);

두 수를 입력 받고 tree에 저장한 후 DFS를 돌려준다.

루트는 1번 노드이며 루트의 깊이는 0이다.

 

void DFS(int node, int d) {
	check[node] = true;
	depth[node] = d;
	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (check[next]) continue;
		parent[next][0] = node;
		DFS(next, d + 1);
	}
}

방문한 노드인지 check배열에 체크 후, depth배열에 깊이를 저장해준다.

parent의[][0]에 한칸 위의 부모를 저장해준다.

 

void setParent() {
	for (int j = 1; j < MAX_DEPTH; j++) {
		for (int i = 1; i < MAX_NODE; i++) {
			parent[i][j] = parent[parent[i][j - 1]][j - 1];
		}
	}
}

parent[i][j] = parent[parent[i][j-1]][j-1]

node   :      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
parent[.][0]: 0 1 1 2 2 2 3 3 4 4  5  5  7  7  11
parent[.][1]: 0 0 0 1 1 1 1 1 2 2  2  2  3  3  5
parent[.][2]: 0 0 0 0 0 0 0 0 1 1  1  1  1  1  2
...

setParent를 돌리면 위와 같은 형태로 되어있을 것이다.

0에는 부모, 1에는 조부모.. 형태로 들어가 있다.

 

int LCA(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (depth[y] - depth[x] >= (1 << i)) {
			y = parent[y][i];
		}
	}
	if (x == y) return x;
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (parent[x][i] != parent[y][i]) {
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	return parent[x][0];
}

이후 LCA를 돌려준다.

우선 2번째 매개변수 y쪽이 더 높은 depth를 가지도록 순서를 변경해준다.

y가 x와 같은 깊이를 가질 때까지 끌어올려주고 y를 해당 깊이의 조상으로 값을 변경해준다.

x와 y가 같다면 이가 최소 공통 조상이므로 return 해준다.

같지 않다면 더 위로 올라가 최소 공통 조상을 찾아야 한다.

한칸씩 위로 올라가며 둘이 같지 않다면 각각 부모의 값으로 변경해준다.

둘이 같다면 최소 공통 조상이므로 이를 return 해준다.

 

#include <iostream>
#include <vector>
using namespace std;

#define MAX_NODE 100001
#define MAX_DEPTH 17 // 2^17 > 100000
int parent[MAX_NODE][MAX_DEPTH];
int depth[MAX_NODE];
bool check[MAX_NODE];
vector<int> tree[MAX_NODE];

void DFS(int node, int d) {
	check[node] = true;
	depth[node] = d;
	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (check[next]) continue;
		parent[next][0] = node;
		DFS(next, d + 1);
	}
}

void setParent() {
	for (int j = 1; j < MAX_DEPTH; j++) {
		for (int i = 1; i < MAX_NODE; i++) {
			parent[i][j] = parent[parent[i][j - 1]][j - 1];
		}
	}
}

int LCA(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (depth[y] - depth[x] >= (1 << i)) {
			y = parent[y][i];
		}
	}
	if (x == y) return x;
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (parent[x][i] != parent[y][i]) {
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	return parent[x][0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	DFS(1, 0);
	setParent();
	cin >> m;
	for (int i = 1; i < m; i++) {
		int u, v;
		cin >> u >> v;
		cout << LCA(u, v) << "\n";
	}
	return 0;
}

전체 코드

 

알고리즘

- 자료 구조

- 트리

- 최소 공통 조상

- 희소 배열