[알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상 알고리즘

1. 정의

: 주어진 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘

 

 

 

2. 예시

- 위와 같은 트리가 있을 때

1) 6번과 7번의 최소 공통 조상은 3

2) 5번과 5번의 최소 공통 조상은 1

3) 4번과 8번의 최소 공통 조상은 4

4) 2번과 3번의 최소 공통 조상은 1

 

 

 

3. LCA 알고리즘 접근 방식

- 각 노드의 depth를 구한다.

- 위의 예시에서 1번 노드의 depth는 1이고 2, 3, 4번 노드는 5,6,7,8번 노드는 3이 된다.

- 만약 두 노드의 depth가 서로 다르면 작은 것에 맞춰 바꿔준다.

 

1) 예를 들어 4번과 7번의 최소 공통 조상을 구한다고 한다면

① depth 구하기 4번은 2, 7번은 3

② 2로 depth를 맞춰주기 depth를 낮추기 위해서는 그 부모로 접근하면 된다. 따라서 7의 부모는 3이므로 depth는 2가 되고 노드는 3이 된다.

③ 두 노드의 depth가 같기 때문에 노드를 비교하고 서로 같다면 현재의 값이 최소 공통 조상이 되고, 다르다면 둘 다 부모로 접근하고 비교하는 과정을 반복한다.

 

 

 

4. 코드

- 백준 11437 LCA 문제 참조

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class LCA {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int[] depth, parent;	
	static ArrayList<Integer>[] adj;
	public static void main(String[] args) throws Exception{
		int N = Integer.parseInt(br.readLine());
		
		adj = new ArrayList[N+1];
		depth = new int[N+1];
		parent = new int[N+1];
		for(int i = 0; i < N+1; i++) {
			adj[i] = new ArrayList<>();
		} 
		for(int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			
			adj[node1].add(node2);
			adj[node2].add(node1);
		}
		
		dfs(1, 1, 0);
		int M = Integer.parseInt(br.readLine());
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			
			int res = LCA(node1, node2);
			sb.append(res + "\n");
		}
		System.out.println(sb);
	}
	private static void dfs(int cur, int d, int p) {
		depth[cur] = d;
		parent[cur] = p;
		
		for(int i = 0, size = adj[cur].size(); i < size; i++) {
			int next = adj[cur].get(i);
			if(next == p) continue;
			dfs(next, d+1, cur);
		}
	}
	private static int LCA(int n1, int n2) {
		int depth1 = depth[n1];
		int depth2 = depth[n2];
		
		while(depth1 > depth2) {
			n1 = parent[n1];
			depth1--;
		}
		while(depth2 > depth1) {
			n2 = parent[n2];
			depth2--;
		}
		
		while(n1 != n2) {
			n1 = parent[n1];
			n2 = parent[n2];
		}
		return n1;
	}
}