hyeoneee's blog

LCA는 트리를 이용해서 최단거리 알고리즘을 구하는 것이다.

최소 공통조상을 구하는 알고리즘이다. Lowest Common Ancestor

구현

0. dfs or bfs depth , parent[N][K] : N번 노드의 2^K번째 조상 기록

parent[2][0] = 2번 노드의 첫번째 조상
parent[2][1] = 2번 노드의 두번째 조상
parent[2][2] = 2번 노드의 네번째(2^2) 조상

dfs로 구현하면 stack이 터질 수 있으니, bfs로 구현하는 것이 좋다.

2^K번째 조상을 기록 한다는것이 잘 이해가 안갈 수 있다. 왜 2^K번째 조상을 기록할까? 시간복잡도를 줄이기 위해서이다.

다음을 보자. 1에서 12로 이동할때 

이진법으로 움직이면?
1->2->-3->4->5->6->7->8->9->10  ->11         ->12 :  한칸씩 뛰면 11번 이동, 비효율적임
1--------(2^3)---------->9-----(2^1)---->11-(2^0)->12 :  2진법으로 움직이면 3번 이동, 효율적임

규칙을보면 다음과 같은 점화식을 얻을 수 있다.

parent[N][K] = parent[parent[N][K-1]][K-1];

A ------------> C                parent[A][4] = C
1               17

A ----- B ----> C                parent[A][3] = B , parent[B][3] = C
1        9        17               parent[A][4] = parent[parent[A][3]][3]

1. LCA 로직

 1) 양쪽 노드중 깊이가 깊은 것을 끌어올려 깊이를 맞춘다.( 2진법으로 뛸 수 있는 만큼 높이 뛰기)

 2) if(a == b) return a;

 3) else 높이가 맞춰진 양쪽 노드를 동시에 끌어올린다. 

    단 2진법으로 뛸수 있는만큼 뛰는데, ***부모가 다를경우에만 점프

 4) return parent[a][0]; // a또는 b의 부모 

샘플코드

BFS

    static int MAX =18;
    static int[] depth = new int[MAX];
    static int[][] parent = new int[MAX][32];
    // 2^k = N -> k = logN : parent배열의 열의 사이즈는 logN
    // 2^10 = 10^3 , 2^40 = 2^10^4 = 10^3^4 = 10^12
    // 2^17 = 13만 , 2^18 = 26만 , 2^20 = 104만

    static boolean[] visited = new boolean[MAX];
    static ArrayList<Integer>[] adj = new ArrayList[MAX];
    
    static void bfs(int now) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(now);

        while (!q.isEmpty()) {
            now = q.poll();
            visited[now] = true;
            for (int next : adj[now]) {
                if (visited[next]) continue;

                parent[next][0] = now;
                for (int j = 1; j < MAX; j++) {
                    parent[next][j] = parent[parent[next][j - 1]][j - 1];
                }

                depth[next] = depth[now] + 1; //// next의 depth는 현재의 depth++;
                q.add(next);

            }
        }
    }

LCA

    static int LCA(int a, int b) {
        // detph 맞추기
        // 0. 항상 a보다 b가 아래에 있는 상태로 만들어주기
        if (depth[a] > depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        //1. 양쪽 노드의 깊이를 맞춰주기 (B를 A가 있는 depth까지 끌어올리기)
        // 1 ---------->12 몇층 이동할까?
        // 12---->4-->2->1
        for (int i = MAX-1; i >= 0; i--) {
            if (depth[b] - depth[a] >= (1 << i)) { // 2^i : 이동할 수 있는만큼 이동하기
                b = parent[b][i];
            }
        }

        // 2. a,b 높이가 맞춰진 상태 - 현재 위치가 LCA인 경우?
        if (a == b) { return a; }
        //3. 양쪽을 동시에 2진법으로 끌어올릴수 있는 만큼 끌어올리는데,단 부모가 다르면 이동
        for (int i = MAX-1; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) { //부모가 다르면 이동
                a = parent[a][i];
                b = parent[b][i];
            }
        }

        return parent[a][0];
    }