[BOJ] 백준 3584번 가장 가까운 공통 조상 자바 풀이

BOJ 3584번 가장 가까운 공통 조상 자바(java) 풀이

• 랭크 : 골드4
• 백준 온라인 저지(BOJ) 3584번 가장 가까운 공통 조상 문제 자바 풀이
• 백준 3584번 가장 가까운 공통 조상

문제정리

1. 테스트 케이스와 트리를 구성하는 노드의 수 N이 주어진다.
2. 트리를 구성하는 간선 정보가 주어질 때, A B가 주어지면 A가 B의 부모라는 뜻이다.
3. 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어진다.

• 이때 두 노드의 가장 가까운 공통 조상을 출력한다.

문제풀이

이 문제는 LCA(Lowest Common Ancestor)문제 입니다.
LCA를 검색하면 정리된 많은 자료들을 볼 수 있습니다.
만약 트리의 루트가 어떠한 노드로 고정되어 있다면 dfs를 통해 탐색할 수 있습니다.
하지만 이 문제는 루트가 정해져있지 않기 때문에 아래에서 위로 올라가는 방식을 이용해야 합니다.
두 정점의 높이를 같게하고 거기서 하나씩 똑같이 올려 가면서 같은 정점이 나올때까지 while문을 반복합니다.
같은 depth에서 시작했기에 depth를 똑같이 증가시키다 만난 같은 정점이 가장 가까운 공통 조상이 됩니다.
예시 그림을 기준으로 설명드리겠습니다. (15와 3의 공통조상 찾기)

1. 부모를 타고 올라가면서 1이 될때까지 올라가며 각 점의 depth를 구합니다. (15은3, 3은 4)
2. 3의 depth가 더 깊으므로 3의 depth를 1 줄여서 맞추어 줍니다.(16에 위치하게 됨)
3. 여기서 동시에 부모를 타고 한 칸 올라갑니다. (15->6, 16->10)
4. 또 한칸 올라갑니다(15->6->4, 16->10->4) 이제 같아졌으므로 가장 가까운 공통 조상은 4임을 알 수 있습니다.

소스 코드

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

class Main {    
    static int vertexNum;
    static int a, b;    
    static int[] parent;
    static ArrayList<ArrayList<Integer>> child;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testNum = Integer.parseInt(br.readLine());

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

            parent = new int[vertexNum+1];

            // 주어진 점들로 트리 만들기
            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]);
                parent[b] = a;
                child.get(a).add(b);
            }

            // 공통 조상을 구할 두 노드
            String[] temp2 = br.readLine().split(" ");
            a = Integer.parseInt(temp2[0]);
            b = Integer.parseInt(temp2[1]);

            int a_depth = get_depth(a);
            int b_depth = get_depth(b);

            int same = solve(a, a_depth, b, b_depth);
            System.out.println(same);
        }

        bw.flush();
        bw.close();
        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 int get_depth(int n){
        int ret = 0;
        int cur = n;
        while(cur != 0) {
            ret++;
            cur = parent[cur];
        }
        return ret-1;
     }
}