Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

1. 가장 가까운 공통 조상

3584번

LCA에 대해 알아 봅시다. 한 쌍의 LCA만 구하면 되므로 아직은 효율적인 구현이 필요하지 않습니다.

이번 문제는 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 문제이다.

LCA란?
Lowest Common Ancestor로, 최소 공통 조상을 찾는 알고리즘을 말하며,
트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드를 찾는 것이다.

Java / Python

• Java

import java.io.*;
import java.util.*;

public class Main {
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		while (T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			parent = new int[N + 1];
			ArrayList<Integer>[] list = new ArrayList[N + 1];

			for (int i = 0; i <= N; i++) {
				list[i] = new ArrayList<>();
			}

			for (int i = 0; i < N - 1; i++) {
				st = new StringTokenizer(br.readLine());

				int p = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());

				parent[c] = p;
				list[p].add(c);
			}
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			int u_depth = getDepth(u);
			int v_depth = getDepth(v);

			bw.write(LCA(u, u_depth, v, v_depth) + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	public static int getDepth(int i) {
		int cnt = 0;
		int now = i;
		while (now != 0) {
			cnt++;
			now = parent[now];
		}
		return cnt - 1;
	}

	public static int LCA(int x, int x_depth, int y, int y_depth) {
		// 깊이가 같아지게 한다.
		if (x_depth > y_depth) {
			while (x_depth != y_depth) {
				x_depth--;
				x = parent[x];
			}
		} else if (x_depth < y_depth) {
			while (x_depth != y_depth) {
				y_depth--;
				y = parent[y];
			}
		}
		while (x != y) {
			x = parent[x];
			y = parent[y];
		}

		return x;
	}
}

• Python

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    parent = [0 for _ in range(N+1)] # 각 노드의 부모노드 저장
    for _ in range(N-1):
        p,c = map(int,input().split())
        parent[c] = p # 부모 노드 저장

    u, v = map(int,input().split())
    u_p = [u]
    v_p = [v]

    while parent[u]:
        u_p.append(parent[u])
        u = parent[u]

    while parent[v]:
        v_p.append(parent[v])
        v = parent[v]

    # 같은 레벨로
    u_level = len(u_p)-1
    v_level = len(v_p)-1

    while u_p[u_level] == v_p[v_level]: # 부모 노드가 다를 때까지 
        u_level -= 1
        v_level -= 1

    print(u_p[u_level + 1])