[BOJ] 백준 3584. 가장 가까운 공통 조상

문제

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

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

---

풀이

 가장 가까운 공통 조상을 찾는 문제입니다. LCA의 풀이법인, 세그먼트 트리나, Sparse table을 사용하지 않고,  parents, check 배열을 통해 해결했습니다. 

 

 우선 입력이 부모와 자식이 구분되기 때문에, 입력을 받으며 해당 정점의 부모를 parents 배열에 입력합니다. 

 

 그리고 공통 조상을 구할 노드 중 하나를 parents 배열을 통해 타고 올라가면서, 방문 시 check 배열을 true로 바꾸어줍니다.

 

 나머지 하나의 노드를 다시 parents 배열을 타고 올라가면서 check 배열을 확인하는데, 만약 check 배열이 true라면 해당 정점이 가장 가까운 공통 조상입니다.

---

소스코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N;
    static int A, B;
    static int ans;
    static int[] parents;
    static boolean[] checked;

    public static void main(String[] args) {
        int T = sc.nextInt();
        for(int tc=0;tc<T;tc++){
           input();
           findLCA();
           System.out.println(ans);
        }
    }

    static void input(){
        N = sc.nextInt();
        parents = new int[N+1];
        checked = new boolean[N+1];
        for(int i =0; i<N-1;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            parents[ed] = st;
        }
        A = sc.nextInt();
        B = sc.nextInt();
    }

    static void findLCA(){
        int temp = A;
        while(temp != 0){
            checked[temp] = true;
            temp = parents[temp];
        }
        int temp2 = B;
        while(temp2 != 0){
            if(checked[temp2]) {
                ans = temp2;
                return;
            }
            temp2 = parents[temp2];
        }
    }
}