LCA - Lowest Common Ancestor (최소공통조상)

기본문제

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

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

 

'트리'에서 두 정점간의 공통 조상 중 가장 가까운 조상의 번호를 찾는 알고리즘이다. O(logn)

(0번노드가 첫 노드)

 

<O(n)>

기본 버전이다. O(n)

코드 이해하기가 굉장히 쉽다. 하지만 사용하진 않을 것. LCA 알고리즘이 크게 어떻게 돌아가는지 파악하기만 하면 됨.

int depth[MAX], parent[MAX];
void dfs(int curr) {
	vst[curr] = true;

	for (int next : adj[curr]) {
		if (!vst[next]) {
			depth[next] = depth[curr] + 1;
			parent[next] = curr;
			dfs(next);
		}
	}
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v); 

	//u,v 깊이 맞추기
	while (depth[u] != depth[v])
		u = parent[u];

	//LCA까지 끌어올리기
	while (u != v) {
		u = parent[u];
		v = parent[v];
	}

	return u;
}

---

<O(logn)>

위 기본버전을 dp로 최적화 한 것. 전처리하는데 O(n), lca수행시간은 O(logn)

각 정점의 depth를 활용해서 LCA를 구해낸다.

 

필요한 것 : 

*depth[i] :

    root ~ i 거리

*parent[i][j] :

    i번 정점의 (1<<j)번째 조상.

    parent[i][j+1] = parent[ parent[i][j] ][ j ] 를 만족한다. (1<<j+1 = 1<<j + 1<<j)

ex)i번정점의 2^3번째 조상은 i번정점의 2^2번째 조상의 2^2번째 조상이다.

    

1. dfs를 돌며 p,depth배열을 채워준다.

 

2.LCA함수를 짠다.

int depth[MAX], p[MAX][20], n;
vector<int> adj[MAX];
void dfs(int curr, int prv) {
	//깊이 초기화
	depth[curr] = depth[prv] + 1;
	//조상 dp
	p[curr][0] = prv;
	for (int i = 1; (1 << i) < n; i++)
		p[curr][i] = p[p[curr][i - 1]][i - 1];

	//dfs
	for (int next : adj[curr]) 
		if (next != prv) 
			dfs(next, curr);			
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	int log = 1;
	for (log = 1; (1 << log) <= depth[u]; log++);
	log--;

	for (int i = log; i >= 0; i--)
		if (depth[u] - (1 << i) >= depth[v])
			u = p[u][i];

	if (u == v) return u;
	for (int i = log; i >= 0; i--) {
		if (p[u][i] != 0 && p[u][i] != p[v][i]) {
			u = p[u][i];
			v = p[v][i];
		}
	}
	return p[u][0];
}

u의 깊이가 v의 깊이 이하이면서 최대가 되도록 맞춰준 후,

 

u와 v가 같다면 v가 u의 조상인 경우로 바로 u를 반환하면 된다.

 

그 외의 경우, u와 v의 (1<<i)번째 조상이 존재하고, u,v,의 조상이 서로 다를때만 올려준다.

 

올릴수있을 때까지 올린 후에, u,v는 서로 같을 수 없다. p[u][0]가 바로 LCA이다.

 

---

<O(logn)> 

위와 비슷하지만 depth대신에 isAncestor(u,v), u가 v의 조상인지 반환하는 함수를 이용한다.

1.dfs를 돌면서 p, tin(dfs들어간 순서), tout(dfs나온순서) 배열을 그때 그때 초기화 한다.

 

2.tin, tout 배열을 기반으로 isAncestor함수를 짠다.

//u가 v의 조상인지?
bool isAncestor(int u, int v) {
	return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

 

3.LCA함수를 짠다.

int tin[MAX], tout[MAX], p[MAX][20], n; 
vector<int> adj[MAX];
//p를 그때그때 초기화.
void dfs(int curr, int parent) {
	tin[curr] = ++timer;
	p[curr][0] = parent;
    //n은 정점 수. 
	for (int i = 1; (1<<i) < n; i++)
		p[curr][i] = p[p[curr][i - 1]][i - 1];

	for (int next : adj[curr]) 
		if (next != parent)
			dfs(next, curr);
	
	tout[curr] = ++timer;
}

//u가 v의 조상인지?
bool isAncestor(int u, int v) {
	return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

int LCA(int u, int v) {
	if (isAncestor(u, v)) return u;
	if (isAncestor(v, u)) return v;
	//u가 lca(u,v)의 바로밑에 있을 때 까지 2^i씩 위로 올라감
    //단, p의 2^i번째 부모가 반드시 있어야함. i엔 그냥 한계치(19) 박아버려도 됨
    for (int i = 19; i >= 0; i--)
		if (p[u][i] != 0 && !isAncestor(p[u][i], v))
			u = p[u][i];
	return p[u][0];
}

두 방법 모두 숙지해 두자