백준 3584 - 가장 가까운 공통 조상 (JAVA)

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

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

 

 

 

 

루트노드가 1이 아닌점을 주의해서 풀이해주시면 됩니다. 

 

 

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

public class Main {
    static int T, N;
    static int [] parent, depth, visits;
    static List<Integer> [] list;

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

        T = Integer.parseInt(br.readLine());

        for (int test_case=1; test_case<=T; test_case++){
            N = Integer.parseInt(br.readLine());
            list = new ArrayList[N+1];
            parent = new int [N+1];
            depth = new int [N+1];
            visits = new int [N+1];

            for (int i=1; i<=N; i++){
                list[i] = new ArrayList<>();
            }
            for(int i=0; i<N-1; i++){
                st = new StringTokenizer(br.readLine());
                int tmp1 = Integer.parseInt(st.nextToken());
                int tmp2 = Integer.parseInt(st.nextToken());
                if (visits[tmp2]!=1) visits[tmp2]=1; // 체크 처리 -> 너는 루트가 될 수 없다
                list[tmp1].add(tmp2);
                list[tmp2].add(tmp1);
            }
            // 루트 노드를 찾는 과정 필요
            int root = 0;
            for (int i=1; i<=N; i++){
                if (visits[i]!=1) {
                    root = i;
                    break;
                }
            }
//            System.out.println("root node : " + root);

            init(root,1,0);

            st = new StringTokenizer(br.readLine());
            int tmp1 = Integer.parseInt(st.nextToken());
            int tmp2 = Integer.parseInt(st.nextToken());
            int ans = LCA(tmp1, tmp2);
            System.out.println(ans);
        }
    }

    static void init(int cur,int h, int from){
        depth[cur] = h;
        parent[cur] = from;
        for (int next : list[cur]){
            if (next != from){
                init(next, h+1, cur);
            }
        }
    }

    static int LCA(int a, int b){
        int ah = depth[a];
        int bh = depth[b];

        while(ah>bh){
            a = parent[a];
            ah--;
        }
        while(bh>ah){
            b = parent[b];
            bh--;
        }

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

        return a;
    }
}