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

[WonYong-Jang]

Lowest Common Ancestor

가장 가까운 위치의 공통 조상을 찾는데 쓰이거나 두 노드의 가장 가까운 거리를 찾는데 사용

LCA

• 단순하게 loop 를 이용 / 시간초과 날 가능성 / O(N)
• parent : 노드의 부모노드를 저장
• depth : 트리의 깊이를 저장

  시나리오

  1) 두 노드가 주어지게 되면 두 노드의 깊이를 구함 ( depth 배열 이용 ) 2) 두 노드들 중 더 깊은 곳에 있는 노드를 더 얖은 곳에 있는 노드 위치까지 끌어 올려줌 2-1) 부모노드로 계속 한칸씩 끌어올리면서 깊이를 확인 / 두 노드가 같은 깊이 상태까지 3) 두 노드 깊이가 같으나 두 노드의 값이 같지 않다면 두 노드 모두 부모노드로 끌어올리면서 같은지 확인 3-1) 두 노드가 같아질때가 최소 공통 조상

public class baek11437 {

    static int N, M;
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
    static int[] parent = new int[50005];
    static int[] depth = new int[50005];
    public static void main(String[] args) throws IOException {

        int dx=0, dy=0;
        for(int i=1; i<= N-1; i++)
        {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());
            adj.get(dx).add(dy);
            adj.get(dy).add(dx);
        }

        dfs(1,1,0); // parent, depth 배열 완성하기 

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for(int i=1; i<= M; i++)
        {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());

            int xDepth = depth[dx];
            int yDepth = depth[dy]; // 각각의 depth 가져와서 확인!

            while(xDepth > yDepth) // x 가 클 경우 낮춰주면서 부모노드로 이동 
            {
                dx = parent[dx];
                xDepth--;
            }

            while(xDepth < yDepth)
            {
                dy = parent[dy];
                yDepth--;
            }

            while( dx != dy ) // 같은 depth 일때 둘다 부모노드로 올라가면서 찾기 
            {
                dx = parent[dx];
                dy = parent[dy];
            }

            System.out.println(dx);
        }
    }
    public static void dfs(int cur, int d, int p) // 현재 노드, 깊이, 부모 노드 
    {
        depth[cur] = d;
        parent[cur] = p;
        for(int next : adj.get(cur))
        {
            if(next != p) // 해당 노드에서 depth 가 더 깊은 곳으로만 이동 / 부모노드로 이동하지 않는다
            {
                dfs(next, d+1, cur); // 다음 depth 로 이동 / 현재 노드가 부모 노드가 됨 
            }
        }
    }
}

LCA2

DP를 이용하여 해결

• 시간 복잡도 O(logN) / 쿼리가 함께 존재할 경우 O(MlogN)

시나리오

1) 깊이가 더 깊은 노드를 깊이가 더 낮은 노드까지 노드를 올려준다

• 이때 노드의 조상들을 이용 / 2^k 번째 조상 중 가장 큰 조상부터 조사함

public class baek11438 {

    static int N, M, max_level;
    static final int MAX_NODE = 100005;
    static int[] depth = new int[MAX_NODE]; // 노드의 깊이(레벨) 
    static int[][] parent = new int[MAX_NODE][20]; // parent[x][y] :: x 의 2^y번째 조상을 의미  
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(); 
    public static void main(String[] args) throws IOException {

        max_level = 0;
        int result =1;
        while(result < N) // max_level 구하기 
        {
            result *= 2;
            max_level++;
        }

        int dx =0, dy=0;

        depth[0] = -1; // 루트 노드 깊이를 0으로 만들어 주기 위해 ! 
        makeTree(1,0); // 트리 만들기 !! 

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for(int i=1; i<= M; i++)
        {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());

            if(depth[dx] != depth[dy]) // 두 노드의 깊이가 다를 경우 같게 맞춰 줘야함 
            {
                if(depth[dx] > depth[dy]) // dy 의 깊이가 더 크다라고 가정하고 끌어올린후 깊이를 같게 만든다 
                { 
                    int tmp = dx;
                    dx = dy;
                    dy = tmp;
                }

                for(int k = max_level; k >= 0; k--)
                {
                    if(depth[dx] <= depth[parent[dy][k]])
                        dy = parent[dy][k];
                }
            }

            int lca = dx;

            if(dx != dy)
            {
                for(int k = max_level; k >= 0; k--)
                {
                    if(parent[dx][k] != parent[dy][k])
                    {
                        dx = parent[dx][k];
                        dy = parent[dy][k];
                    }
                    lca = parent[dx][k];
                }
            }
            bw.write(lca+"\n");
        }
        bw.flush();
    }
    public static void makeTree(int cur, int p)
    {
        depth[cur] = depth[p] + 1; // 부모 노드의 깊이에서 +1 ==> 현재 노드 깊이 
        parent[cur][0] = p; // 바로 위 부모 노드 

        /*
            Node 의 2^i 번째 조상은 tmp 의 2^(i-1) 번째 조상의 2^(i-1)번째 조상과 
            같다는 의미
            예 ) i =3 일때
            Node의 8번째 조상은 tmp(Node의 4번째 조상)의 4번째 조상과 같다.
            i=4 일때는 Node 16번째 조상은 Node 의 8번째 조상(tmp)의 8번째와 같다.
         */
        for(int i=1; i<= max_level; i++)
        {
            int tmp = parent[cur][i-1];
            parent[cur][i] = parent[tmp][i-1];
        }

        for(int next : adj.get(cur)) // 자식 노드 내려가면서 확인 
        {
            if(next != p) // 사이클 방지 아래로만 내려가기 
            {
                makeTree(next, cur);
            }
        }
    }

}

LCA2 를 이용한 정점들간의 거리

• dist[parent] 배열의 의미는 1(root)에서 부모까지 내려온 거리이고 cost 값은 부모와 자식 노드의 거리 둘을 더하게 되면 1에서 자식까지의 거리를 생성 가능 ==> dist[cur] = dist[parent] + cost

public class Main {

    static int N, M, max_level;
    static int max_node = 40005;
    static int[][] par = new int[max_node][20];
    static int[] depth = new int[max_node];
    static int[] cost = new int[max_node];
    static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>();
    public static void main(String[] args) throws IOException {

        max_level = 0;
        int mul = 1;
        while(N > mul) { // 확인 
            mul *= 2;
            max_level++;
        }

        int dx = 0, dy = 0, c = 0;
        for(int i=1; i<= N-1; i++)
        {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            adj.get(dx).add(new Node(dy, c));
            adj.get(dy).add(new Node(dx, c));
        }
        depth[0] = -1;
        dfs(1, 0, 0);

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for(int i=1; i<= M; i++)
        {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());

            int result = 0;
            int rdx = dx, rdy = dy;
            if(depth[dx] != depth[dy])
            {
                if(depth[dx] > depth[dy])
                {
                    int tmp = dx;
                    dx = dy;
                    dy = tmp;
                }

                for(int k = max_level; k >= 0; k--)
                {
                    if(depth[dx] <= depth[par[dy][k]]) {
                        dy = par[dy][k];
                    }
                }
            }

            int lca = dx;

            if(dx != dy)
            {
                for(int k = max_level; k >= 0; k--)
                {
                    if(par[dx][k] != par[dy][k])
                    {
                        dx = par[dx][k];
                        dy = par[dy][k];
                    }
                    lca = par[dx][k];
                }
            }

            result = ( cost[rdx] + cost[rdy] ) - ( 2 * cost[lca] );
            bw.write(result+"\n");
        }
        bw.flush();
    }
    public static void dfs(int cur, int p, int c)
    {
        depth[cur] = depth[p] + 1;
        cost[cur] = c;
        par[cur][0] = p;

        int tmp = 0;
        for(int i=1; i<= max_level; i++)
        {
            tmp = par[cur][i-1];
            par[cur][i] = par[tmp][i-1];
        }

        for(Node next : adj.get(cur))
        {
            if(next.dx != p)
            {
                dfs(next.dx, cur, next.cost + c);
            }
        }
    }
}

출처 링크 : https://www.crocus.co.kr/660

[WonYong-Jang]

추천 문제

11438번: LCA 2

1761번: 정점들의 거리

8012번: Byteasar the Travelling Salesman

15480번: LCA와 쿼리 (★)

1396번: 크루스칼의 공 (★)

[WonYong-Jang]

3176번 도로 네트워크

public class Main {

    static int N, K, max_level;
    static final int max_node = 100005;
    static int[][] maxDp = new int[max_node][20];
    static int[][] minDp = new int[max_node][20];
    static int[][] parent = new int[max_node][20];
    static int[] depth = new int[max_node];
    static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>(); 
    public static void main(String[] args) throws IOException {

        depth[0] = -1;
        dfs(1,0,0);

        make_dp();

        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        for(int i=1; i<= K; i++)
        {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());

            int tx = dx, ty = dy;
            int ansMax = -1, ansMin = Integer.MAX_VALUE;
            if(depth[dx] != depth[dy] )
            {
                if(depth[dx] > depth[dy]) {
                    int tmp = dx;
                    dx = dy;
                    dy = tmp;
                }

                for(int k = max_level; k >= 0; k--)
                {
                    if(depth[dx] <= depth[parent[dy][k]]) 
                    {
          // 주의 dy 갱신하기 전에 먼저 (위치 주위!!)
          //  dx 는 고정이기 때문에 dy 만 해주는 것 주의!!! // dx 도 같이 비교했다가 답 틀림
                        ansMin = min(ansMin, minDp[dy][k]); 
                        ansMax = max(ansMax, maxDp[dy][k]); 
                        dy = parent[dy][k];
                    }
                }
            }

            int lca = dx;

            if(dx != dy)
            {
                for(int k = max_level; k >= 0; k--)
                {
                    if(parent[dx][k] != parent[dy][k])
                    {
                        ansMax = max(ansMax, max(maxDp[dx][k], maxDp[dy][k]));
                        ansMin = min(ansMin, min(minDp[dx][k], minDp[dy][k]));
                        dx = parent[dx][k];
                        dy = parent[dy][k];
                    }
                    lca = parent[dx][k];
                }
            }
            if(dx != lca)
            {
                ansMin = min(ansMin, min(minDp[dx][0], minDp[dy][0]));
                ansMax = max(ansMax, max(maxDp[dx][0], maxDp[dy][0]));
            }
            bw.write(ansMin+" "+ansMax+"\n");
        }
        bw.flush();
    }
    public static void dfs(int cur, int p, int cost)
    {
        depth[cur] = depth[p] + 1;
        parent[cur][0] = p;

        maxDp[cur][0] = cost;
        minDp[cur][0] = cost;

        for(int i =1; i<= max_level; i++)
        {
            int temp = parent[cur][i-1];
            parent[cur][i] = parent[temp][i-1];
        }

        for(Node next : adj.get(cur))
        {
            if(next.dx != p)
            {
                dfs(next.dx, cur, next.cost);
            }
        }
    }
    public static void make_dp()
    {
        for(int jump = 1; jump <= max_level; jump++)
        {
            for(int cur =1; cur <= N; cur++)
            {
                int tmp = parent[cur][jump-1];
                maxDp[cur][jump] = max(maxDp[cur][jump-1], maxDp[tmp][jump-1]);
                minDp[cur][jump] = min(minDp[cur][jump-1], minDp[tmp][jump-1]);
            }
        }
    }
}

[WonYong-Jang]

LCA와 쿼리 (15480 )

• 쿼리마다 root 노드가 변경되는 문제!

  일단 임의의 루트로 두고 lca를 구하는 sparse table을 만들어 놓고 r, u, v,에 대한 정답은

  (r, u) / (r, v) / (u, v) 의 lca들의 depth들 중 가장 큰 값!!

LCA와 쿼리 2 ( 13511 )

• k 번째 수 구하는 구하기
• lca구하여 왼쪽과 오른쪽 높이를 각각 구한다.
• 만약 if(leftHeight >= k ) 라면 왼쪽에서 k번째를 찾고
• 그렇지 않은 경우 오른쪽에서 k 번째를 찾는데 이때 k- leftHeight 의 값을
• rightHeight 에 빼준 값을 k로 지정하여 sparse table 를 이용하여 노드를 찾는다.

leftDepth = depth[dx];
rightDepth = depth[dy];
lcaDepth = depth[lca];
leftHeight = leftDepth - lcaDepth + 1;
rightHeight = rightDepth - lcaDepth + 1;
int ans = 0, target =0, sum = 1;

if(leftHeight >= k) { // 왼쪽에서 k 번째 찾아 
target = dx;
}
else if(leftHeight < k) {
temp = k - leftHeight;
k = rightHeight - temp;
target = dy;
}