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

---

문제 링크 

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

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

---

문제 풀이

- 두 노드 간의 가장 가까운 공통 조상(Lowest Common Ancestor)을 찾음

- 각 노드의 부모 노드(PARENT)와 깊이(DEPTH) 를 구하고, 깊이의 차가 있을 경우 동일하게 맞춘 후 공통 조상 노드를 찾아 감

- 선형 탐색으로 풀이 하여 O(T * N) 시간복잡도 ( 2 ≤ N ≤ 10,000 )

 

LCA(Lowest Common Ancestor) 알고리즘에 대해 알아보도록 하자

*관련 문제
BOJ 11437 LCA

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
  static StringBuilder sb = new StringBuilder();

    static int T, N, A, B, ROOT_NODE;

    static int[] DEPTH, PARENT;

    static List<Integer>[] adj;

    static boolean[] VISIT;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());

        while(T > 0) {
            T -= 1;

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());

            VISIT = new boolean[N + 1];
            DEPTH = new int[N + 1];
            PARENT = new int[N + 1];
            Arrays.fill(PARENT, -1);

            adj = new ArrayList[N + 1];
            for(int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

            for(int i = 1; i <= N - 1; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                PARENT[to] = from;

                adj[from].add(to);
                adj[to].add(from);
            }

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

            pro();
        }
    }

    static void dfs(int x, int _depth) {
        VISIT[x] = true;

        for(int y : adj[x]) {
            if(VISIT[y]) continue;

            DEPTH[y] = _depth + 1;
            dfs(y, _depth + 1);
        }
    }

    static void lca() {
        int depthA = DEPTH[A];
        int parentA = A;

        int depthB = DEPTH[B];
        int parentB = B;

        while(depthA > depthB) {
            depthA -= 1;
            parentA = PARENT[parentA];
        }

        while(depthA < depthB) {
            depthB -= 1;
            parentB = PARENT[parentB];
        }

        while(parentA != parentB) {
            parentA = PARENT[parentA];
            parentB = PARENT[parentB];
        }

        sb.append(parentA).append("\n");
    }
    static void pro() {
        for(int i = 1; i <= N; i++) {
            if(PARENT[i] == -1) {
                ROOT_NODE = i;
                break;
            }
        }

        dfs(ROOT_NODE, 0);
        lca();
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
}