[백준] 3584번. 가장 가까운 공통 조상(JAVA)

문제

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

---

풀이

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            int[] arr = new int[n+1];

            for(int j = 1; j < n; j++){
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                arr[end] = start;
            }
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            Stack<Integer> firstAncestor = new Stack<>();
            Stack<Integer> secondAncestor = new Stack<>();

            firstAncestor.push(first);
            secondAncestor.push(second);
            while(arr[first] != 0){
                firstAncestor.push(arr[first]);
                first = arr[first];
            }
            
            while(arr[second] != 0){
                secondAncestor.push(arr[second]);
                second = arr[second];
            }
            int lca = 0;
            int minSize =Math.min(firstAncestor.size(), secondAncestor.size());

            while(minSize > 0){
                minSize--;
                first = firstAncestor.pop();
                second = secondAncestor.pop();
                if(first == second){
                    lca = first;
                }else{
                    break;
                }
            }
            System.out.println(lca);
        }
    }
}

 

1. 자신의 조상만을 저장하는 배열을 만든다.

2. 이 때 조상으로 0이 나왔다면 루트노드라는 것이다.

3. 이후 스택에 하나씩 넣어준다.

4. 스택 사이즐르 맞춘 후 시작한다.

5. 만약 같은 것이 나왔다면 저장하고 계속 진행한다.

6. 다른 것이 나왔다면, 길이 갈라졌다는 것이기 때문에 저장을 멈추고 끝난다.