[백준] 11437. LCA

문제 링크

[백준] 11437. LCA

풀이 과정

LCA(Lowest Common Ancestor) 기본 문제입니다. 문제 입력 예로 주어진 간선들을 이용해 트리를 구성하면 아래와 같습니다.

먼저, dfs() 메소드로 dfs 탐색을 하며, 모든 노드에 대해 깊이와 부모를 저장해줍니다.

private static void dfs(int from, int d) {
    visit[from] = true;
    depth[from] = d;

    for (int to : adj[from]) {
        if (!visit[to]) {
            parent[to] = from;
            dfs(to, d + 1);
        }
    }
}

이후, 가장 가까운 공통 조상을 알고 싶은 쌍을 입력 받아, 두 정점간의 LCA를 구합니다. lca() 메소드는 다음과 같이 작동합니다.

1. 먼저 두 노드의 깊이가 동일하도록, 깊이가 더 깊은 노드를 더 얕은 노드에 맞춥니다.
2. 이후 부모가 같아질 때까지 반복적으로 두 노드의 부모를 각각 거슬러 올라갑니다.

private static int lca(int a, int b) {
    while (depth[a] != depth[b]) {
        if (depth[a] > depth[b]) {
            a = parent[a];
        } else
            b = parent[b];
    }

    if (a == b) return a;

    while (parent[a] != parent[b]) {
        a = parent[a];
        b = parent[b];
    }

    return parent[a];
}

예를 들어, 위 트리에서 정점 8과 정점 15의 최소 공통 조상을 찾고 싶으면, 먼저 둘의 깊이를 맞춥니다. 깊이가 더 깊은 정점 15가 정점 8의 깊이까지 맞춥니다. 이때, 만약 두 노드의 정점 번호가 같다면, 해당 번호가 최소 공통 조상이 됩니다.

이후, 부모가 같지 않다면 같을 때까지 거슬러 올라갑니다.

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N, M;
    static ArrayList<Integer>[] adj;
    static boolean[] visit;
    static int[] depth;
    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++)
            adj[i] = new ArrayList<>();
        visit = new boolean[N + 1];
        depth = new int[N + 1];
        parent = new int[N + 1];

        for (int i = 0; i < N - 1; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();

            adj[v1].add(v2);
            adj[v2].add(v1);
        }

        dfs(1, 0);

        M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            System.out.println(lca(sc.nextInt(), sc.nextInt()));
        }
    }

    private static void dfs(int from, int d) {
        visit[from] = true;
        depth[from] = d;

        for (int to : adj[from]) {
            if (!visit[to]) {
                parent[to] = from;
                dfs(to, d + 1);
            }
        }
    }

    private static int lca(int a, int b) {
        while (depth[a] != depth[b]) {
            if (depth[a] > depth[b]) {
                a = parent[a];
            } else
                b = parent[b];
        }

        if (a == b) return a;

        while (parent[a] != parent[b]) {
            a = parent[a];
            b = parent[b];
        }

        return parent[a];
    }
}