[BOJ] 백준 11437번 LCA 자바 풀이

BOJ 11437번 LCA 자바(java) 풀이

• 랭크 : 골드3
• 백준 온라인 저지(BOJ) 11437번 LCA 문제 자바 풀이
• 백준 11437번 LCA

문제정리

1. 1~N번으로 번호가 매겨진 정점들이 주어진다.
2. 루트는 1번이다.
3. 가장 가까운 공통 조상을 알고 싶은 m개의 쌍이 주어진다.
4. n-1개의 트리 상에서 두 정점의 연결 정보가 주어진다. 이때 A B라고 주어질때 A가 부모라는 보장이 없다.

문제풀이

이 문제는 LCA(Lowest Common Ancestor)문제 입니다.
LCA를 검색하면 정리된 많은 자료들을 볼 수 있습니다.
이 문제는 depth를 모두 구하고 부모와 자식간의 관계를 구하여 트리를 만든 다음에
구하고자 하는 정점의 depth를 맞춰준다음 같은 노드가 될 때 까지 부모를 타고 하나씩 올라오면 됩니다.
6과 11의 LCA을 구하는 것을 예로 들겠습니다.

1. 부모 노드가 정해져있지 않기 때문에 모든 노드의 dfs를 돌면서 depth를 구합니다.
   이때 depth가 0인 것은 depth를 아직 구하지 않은 노드이기 때문에 dfs를 물고 들어가서 depth를 update 시켜줍니다.
   루트 노드인 1부터 출발합니다. 1과 연결된 점으로 우선 2가 있습니다.
   그러면 2에는 4,6,5가 있습니다. 재귀로 들어왔기 때문에 4는 depth가 증가한 상태입니다.
   4와 연결된 점에는 2,9가 있는데 2는 이미 depth를 구했고 9를 from값으로 들어갑니다.
   이제 더 이상 9와 연결된 점이 없습니다.(4는 이미 depth가 update됨)
   그러면 4가 from인 context로 돌아와서 이제 9의 부모가 4가 됨을 알 수 있습니다.
   4에 대해서 끝났고 2가 from인 context로 돌아와서 6을 탐색하고 6의 부모는 2임을 update할 수 있습니다.
   이와 같은 방식으로 depth를 가지고 부모와 자식간의 관계를 구할 수 있습니다.
2. 이제 둘 중 depth가 더 작은 것에 기준을 맞춰서 depth를 같게 해줍니다.
   11의 depth가 더 크기 때문에 6에 맞춰서 올려줍니다. 즉 11은 5로 바뀝니다.
3. 그리고 depth를 하나씩 감소시키면서(위로 올리면서) 같은 값이 나올때까지 반복합니다.
   6과 11에서 parent를 이용해 하나씩 올리면 둘다 2가 나오면서 같게 되고 이가 LCA가 됩니다.

BOJ 11437 LCA github 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {    
    static int vertexNum; 
    static ArrayList<ArrayList<Integer>> tree;
    static int m;
    static int[] depth;
    static int[] parent;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력받기
        vertexNum = Integer.parseInt(br.readLine());
        tree = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<vertexNum+1; i++)
            tree.add(new ArrayList<Integer>());

        // 주어진 점들로 트리 만들기
        for(int i=0; i<vertexNum-1; i++){
            String[] temp = br.readLine().split(" ");
            int a = Integer.parseInt(temp[0]);
            int b = Integer.parseInt(temp[1]);
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        depth = new int[vertexNum+1];
        parent = new int[vertexNum+1];
        m = Integer.parseInt(br.readLine());

        // 정점들의 depth 구하기
        dfs(1,1);
        for(int i=0; i<m; i++){
            // 공통 조상을 구할 두 노드
            String[] temp2 = br.readLine().split(" ");
            int a = Integer.parseInt(temp2[0]);
            int b = Integer.parseInt(temp2[1]);

            int same = solve(a, depth[a], b, depth[b]);
            System.out.println(same);
        }

        br.close();
    }

    static int solve(int a, int a_depth, int b, int b_depth){
        // 둘의 depth가 같아질 때까지 위로 올린다.
        if(a_depth > b_depth){
            while(a_depth != b_depth){
                a_depth--;
                a = parent[a];
            }
        }
        else if(a_depth < b_depth){
            while(a_depth != b_depth){
                b_depth--;
                b = parent[b];
            }
        }


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

        return a;
    }

    static void dfs(int from, int cnt) {
        depth[from] = cnt++;
        for(Integer next: tree.get(from)) {
            if(depth[next] == 0) {
                dfs(next, cnt);
                parent[next] = from;
            }
        }
    }
}