[BOJ 3584] 가장 가까운 공통 조상 - JAVA, Gold4

https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

사용한 알고리즘 : LCA(Lowest Common Ancestor, 최소 공통 조상)

 

풀이 전략

위 문제에서 주어진 첫 번째 입력을 그래프로 나타내면 아래와 같다.

문제에서는 16과 7의 가장 가까운 공통 조상인 LCA를 구하라고 주어졌다.

결론부터 말하면 눈에 보이듯 4인데, 이를 알고리즘적으로 어떻게 구할 수 있을지 생각해보자.

 

먼저 LCA를 찾을 각 노드인 16과 7이 루트 노드까지 어떻게 올라가는지 탐색한다.

16은 16->10->4->8

7은 7->6->4->8

경로로 루트 노드까지 이어진다.

 

경로 상의 각 노드들은 16과 7 노드의 조상 노드들이고

결과적으로는 둘 다 루트 노드를 최상위 부모 노드로 갖는다.(둘 다 같은 트리에 속한 노드이므로)

 

그럼 여기서 어떻게 가장 가까운 공통 조상 노드를 찾을 수 있을까?

여러 방법이 있겠지만 나는 스택을 사용했다.

 

후입 선출의 구조를 지닌 스택 구조를 활용했는데,

각 노드가 루트 노드까지 올라가는 과정의 노드들을 스택에 차례로 push한다.

 

그러면 16과 7의 조상 노드들이 아래 그림처럼 Stack에 쌓이게 된다.

최초 상태에서의 두 스택의 꼭대기 값은 루트 노드의 번호이다.(위 그림에서는 8)

그리고 그 이후에 pop한 값이 서로 일치한다는 것은 두 수가 공통된 조상 노드를 가진다는 의미이다.

 

8 = 8   --> 공통 노드

4 = 4   --> 공통 노드

10 != 6  --> 공통 노드 아님

 

따라서 두 수를 비교했을 때 공통된 수가 아니게 될 때까지 비교를하면

마지막으로 공통됐던 값이 LCA가 된다.(위 그림에서는 4)

 

제출코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static int parent[];
    static Stack<Integer> stackA = new Stack<>();
    static Stack<Integer> stackB = new Stack<>();

    static int find_parent(int x, Stack<Integer> stack){
        stack.push(x);
        if(x==parent[x]) return x;
        else return find_parent(parent[x],stack);
    }

    static int find_LCA(){
        int lca=0;
        while(!stackA.isEmpty() && !stackB.isEmpty()){
            int aVal = stackA.pop();
            int bVal = stackB.pop();
            if(aVal==bVal){
                lca=aVal;
            }
            else break;
        }
        return lca;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for(int t=0;t<T;++t){
            int N = Integer.parseInt(br.readLine());
            parent = new int[N+1];
            stackA.clear();
            stackB.clear();
            for(int i=1;i<=N;++i){
                parent[i]=i;
            }

            for(int n=0;n<N-1;++n){
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                parent[B]=A;
            }

            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            find_parent(A,stackA);
            find_parent(B,stackB);

            bw.write(find_LCA()+"\n");
        }
        bw.flush();
        bw.close();
    }
}