12. 최소 공통 조상 (LCA: Lowest Common Ancestor)

최소 공통 조상은 트리구조에서 특정 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 트리구조라는 용어 자체가 생소하신 분들은 나무위키의 트리(그래프) 항목을 참고하시기 바랍니다.

트리(그래프) - 나무위키

https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

LCA(Lowest Common Ancestor) 알고리즘은 일반적으로 앞에서 이야기한 정의에 따라 가장 가까운 위치의 공통 조상을 찾는데 쓰이지만 이는 또한 두 노드의 가장 가까운 거리를 찾는다는 의미도 있기 때문에 노드간 거리를 구할 때도 사용됩니다.

LCA 알고리즘은 단순하게 loop를 이용하여 공통조상을 찾는 방식과 DP나 세그먼트 트리를 이용하여 찾는 방식이 있습니다. 이해와 구현하기는 loop 방식이 편하지만 그만큼 느리다는 단점이 있습니다. 문제를 풀 때에 케이스가 크게 주어지거나 시간이 적게 주어져서 loop 방식으로 탐색하는 식으로는 시간초과가 날 것 같다는 판단이 들면 DP나 세그먼트 트리를 이용하는 방식으로 문제를 푸셔야 합니다. 이번에는 loop 방식의 LCA에 대해 말씀드릴 것이며, 다음 기회에 Algorithm Study 카테고리에서 LCA2라는 백준 알고리즘 저지 문제를 풀이하면서 DP를 이용한 LCA를 설명해드리도록 하겠습니다.

LCA는 트리 구조를 만들어주는 것에서 문제 풀이가 시작됩니다. 일반적인 그래프 문제를 풀이하듯이 List와 Array를 이용하여 트리구조를 생성해줍니다. 만일 root가 특정 노드로 결정되어있을 경우라면 상관없지만 문제에서 주어질 경우 따로 기억해두도록 합니다. 그리고 이제 배열 두 개를 선언해주는데 하나는 노드의 부모노드를 저장해줄 parent 배열이고 다른 하나는 트리의 깊이를 저장해줄 depth 배열입니다. 이름은 제가 임의로 정해준 것이기 때문에 필요에 따라 수정하셔도 상관없습니다. 이제 DFS를 이용하여 root에서부터 시작하여 각 노드별로 부모노드와 깊이를 저장해줍니다. DFS가 끝나게 되면서 전체 노드의 깊이와 부모노드 정보가 저장이 되게 되면 비로소 특정 두 노드의 공통 조상을 찾을 수 있게 됩니다.

두 노드가 주어지게 되면 먼저 두 노드의 깊이를 구합니다. depth 배열을 이용하면 쉽게 해당 노드들의 깊이를 알 수 있게 됩니다. 이제 두 노드들 중에서 더 깊은 곳에 있는 노드를 더 얕은 곳에 있는 노드 위치까지 끌어올려줍니다. 끌어올리는 방법은 간단합니다. 자신의 부모노드로 그리고 그 부모노드로 계속 한칸씩 끌어올리면서 깊이를 확인하는 것입니다. 그렇게 하다보면 두 노드가 언제가는 같은 깊이를 갖는 상태까지 오게 됩니다. 그 상태에서도 두 노드가 같은 조상을 만나지 못했다면 이제 두 노드를 동시에 한 칸씩 더 끌어올려줍니다. 그렇게 두 노드가 같은 부모노드를 만날 때까지 계속 loop를 돌려주게되면 결국 최소 공통 조상을 찾게 됩니다.

문제를 풀어보면서 이해해보겠습니다.

11437번: LCA - Baekjoon Online Judge

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

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

public class Main {
	private static int[] parent;
	private static int[] depth;
	private static BufferedReader br;
	private static StringTokenizer st;
	private static ArrayList<Integer>[] con;
	private static int N;
	private static int a;
	private static int b;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = null;

		N = Integer.parseInt(br.readLine().trim());

		parent = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			parent[i] = -1;
		}
		depth = new int[N + 1];
		con = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			con[i] = new ArrayList<Integer>();
		}
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine().trim());

			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());

			con[a].add(b);
			con[b].add(a);
		}
		dfs(1, 1, 0);
		int M = Integer.parseInt(br.readLine().trim());
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine().trim());

			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());

			int aDepth = depth[a];
			int bDepth = depth[b];

			while (aDepth > bDepth) {
				a = parent[a];
				aDepth--;
			}
			while (bDepth > aDepth) {
				b = parent[b];
				bDepth--;
			}
			while (a != b) {
				a = parent[a];
				b = parent[b];
			}
			System.out.println(a);
		}
	}

	private static void dfs(int cur, int d, int p) {
		depth[cur] = d;
		parent[cur] = p;
		for (int nxt : con[cur]) {
			if (nxt != p) {
				dfs(nxt, d + 1, cur);
			}
		}
	}
}