[ BOJ] 가장 가까운 공통 조상

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

image

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

풀이

처음에는 부모의 노드를 찾아야 하니 탐색을 진행해야 한다고 생각했다.
따라서 BFS를 이용하여 탐색을 진행하려 했는데, 숫자 크기에 따라서 자식과 부모를 구분짓지 않고,
부모 자식 관계를 고려하여 진행해야 하기에 좋지 못한다고 생각하였다.

따라서 부모만을 파악하는 방식으로 바꾸었다.
a와 b의 공통 부모를 파악 해야 한다면,
a의 상위 탐색을 진행하여 진행방향을 모두 체크해준다.
이후 b의 탐색을 진행하면 a가 지나간 가장 첫번째의 자취를 만난다면 그것이 가장 깊은 공통 조상이 될 것이다.

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


class Main {
    static boolean[] visited;
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int T = Integer.parseInt(str[0]);

        for (int i = 0; i < T; i++) {
            str = br.readLine().split(" ");
            int N = Integer.parseInt(str[0]);
            visited = new boolean[N + 1];
            parent = new int[N + 1];
            for (int j = 0; j < N - 1; j++) {
                str = br.readLine().split(" ");
                int a = Integer.parseInt(str[0]);
                int b = Integer.parseInt(str[1]);
                parent[b] = a;
            }
            str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);

            System.out.println(find(a, b));
        }
    }

    static int find(int a, int b) {
        while (parent[a] != 0) {
            visited[a] = true;
            a = parent[a];
        }

        while (parent[b] != 0) {
            if (visited[b]) {
                return b;
            }
            visited[b] = true;
            b = parent[b];
        }

        return a;
    }

}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EA%B0%80%EC%9E%A5%20%EA%B0%80%EA%B9%8C%EC%9A%B4%20%EA%B3%B5%ED%86%B5%20%EC%A1%B0%EC%83%81