[java] 최소 공통 조상 알고리즘

04 Dec 2023

java

최소 공통 조상(Lowest Common Ancestor) 알고리즘은 트리 구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 이 알고리즘을 사용하면 두 노드의 공통 조상을 빠르게 찾을 수 있습니다. 자바를 사용하여 최소 공통 조상 알고리즘을 구현해 보겠습니다.

알고리즘 개요

최소 공통 조상 알고리즘은 다음과 같은 단계로 구현됩니다.

트리를 구성하는 노드들의 부모를 저장하는 배열(parent[])을 생성합니다.
트리를 DFS나 BFS 방식으로 탐색하여 각 노드의 부모를 설정합니다.
각 노드의 깊이(depth[])를 계산합니다.
두 노드의 깊이를 맞추기 위해 더 깊이 있는 노드를 위로 올려줍니다.
두 노드의 깊이가 같아질 때까지 각 노드를 위로 올려주며 공통 조상을 찾습니다.
두 노드의 깊이가 같아진 후에도 두 노드가 같지 않으면, 각 노드를 조상으로 거슬러 올라가면서 공통 조상을 찾습니다.
공통 조상을 찾았다면 결과를 반환합니다.

알고리즘 구현

아래는 자바로 최소 공통 조상 알고리즘을 구현한 예제 코드입니다.

import java.util.*;

class Solution {
    int[] parent;
    int[] depth;

    // 최소 공통 조상 알고리즘 구현
    public int getLowestCommonAncestor(int n, int[][] edges, int x, int y) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        parent = new int[n];
        depth = new int[n];

        dfs(graph, x, -1, 0);

        return lca(y);
    }

    // DFS로 노드의 부모와 깊이 구하기
    private void dfs(List<List<Integer>> graph, int node, int parent, int d) {
        depth[node] = d;
        for (int child : graph.get(node)) {
            if (child != parent) {
                dfs(graph, child, node, d + 1);
                parent[child] = node;
            }
        }
    }

    // 최소 공통 조상 찾기
    private int lca(int node) {
        while (depth[node] != depth[node]) {
            if (depth[node] < depth[node]) {
                node = parent[node];
            } else {
                node = parent[node];
            }
        }
        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        int n = 7;
        int[][] edges = {{0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {3, 6}};
        int x = 4;
        int y = 6;

        Solution solution = new Solution();
        int lowestCommonAncestor = solution.getLowestCommonAncestor(n, edges, x, y);
        System.out.println("최소 공통 조상: " + lowestCommonAncestor);
    }
}

참고 자료

이 알고리즘을 구현하기 위해 다음 자료들을 참고할 수 있습니다.