[BOJ 3584] 가장 가까운 공통 조상(Java)

#문제

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

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

 

#풀이

LCA 알고리즘을 이용해 풀었다. 

입력 시 parent, child 관계를 명시해주기 때문에 인접 노드 리스트에 정보를 양쪽으로 넣어주지 않았다.

child 방향으로 인접 노드 리스트가 구성되었기 때문에, depth 갱신 시 계산된 node에 대해 calculated 여부를 체크하지 않았다.

parent 정보가 이미 있기 때문에 depth 정보만 갱신해준 후 findLCA() 함수를 호출하여 LCA를 찾는다.

 

#유사문제

2021.10.24 - [Alogirthm/BOJ] - [BOJ 11437] LCA (Java)

 

#소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ3584 {

    public static StringBuilder sb;
    public static int T, N;
    public static int[] parent, depth;
    public static ArrayList<Integer>[] childs;

    public static void pro() throws Exception {
        sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for(int j = 0; j < T; j++){
            N = Integer.parseInt(br.readLine());
            parent = new int[N+1];
            depth = new int[N+1];
            childs = new ArrayList[N+1];
            for(int i = 0; i <= N; i++) childs[i] = new ArrayList<Integer>();

            for(int i = 0; i < N-1; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int p = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                parent[c] = p;
                childs[p].add(c);
            }

            // root node 찾기
            // parent가 없는 node
            int root = 0;
            for(int i = 1; i <= N; i++){
                if(parent[i] == 0){
                    root = i;
                    break;
                }
            }

            // depth 계산해주기
            dfs(root, 0);

            // LCA 찾기
            StringTokenizer st = new StringTokenizer(br.readLine());
            sb.append(findLCA(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))).append("\n");
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int n, int d){
        depth[n] = d;
        for(int child : childs[n]) {
            dfs(child, d + 1);
        }
    }

    public static int findLCA(int a, int b){
        // a와 b의 depth가 같아질때까지 depth가 큰 쪽을 parent로 치환
        while(depth[a] > depth[b]){
            a = parent[a];
        }
        while(depth[b] > depth[a]){
            b = parent[b];
        }
        // 같아졌으면, 차례대로 올라가면서 공통조상 찾기
        while(a != b){
            a = parent[a];
            b = parent[b];
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        pro();
    }
}