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

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

해결

트리의 노드는 모두 root node를 부모로 한다.

즉, 모든 노드가 연결되어있다.

따라서 각 노드의 부모 노드를 찾다보면 root node에서 만날 것이다.

💡 다르게 말하자면 트리는 내 부모노드와 내가 공통 조상을 가지고 있다.

 

트리 구조 저장

x, y의 레벨을 찾고 부모 노드를 저장하는 방법은

union-find 알고리즘에서 root Parent를 찾는 방법에서 아이디어를 떠올려 풀었다.

 

union-find 알고리즘의 disjoint set에서 서로 다른 두 노드가 연결되었는지 알기 위해, 

Parent 배열이 존재하고, 두 노드가 연결될 경우 두 노드의 부모를 같게 한다.

 

getParent라는 재귀함수를 통해 두 노드의 부모가 같다면 연결되었다고 판단한다.

 

 

따라서 Parent 배열을 생성한다.

Parent[n1] = n2 라면 'n1의 부모노드는 n2이다.' 라는 뜻이다.

 

 

공통 조상 찾기

내가 공통 조상을 찾으려는 서로 다른 두 노드를 x, y라고 하자.

 

x, y의 레벨(depth, 깊이, 높이)가 같다면 한칸씩 부모노드로 올라가다보면,

처음 부모 노드가 같아지는 노드가 바로 공통 조상이다.

 

 

x, y의 레벨이 다르다면 둘의 레벨을 같게 해주면 된다.

레벨이 더 깊은(키가 큰) 노드를 부모노드로 올리면 된다. x = Parent[x] 의 과정을 거치면 x의 레벨을 낮게할 수 있다 (루트 노드에 가까워진다)

 

 

코드

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int[] Parent = new int[10001]; // Parent[n1] = n2 == n1의 부모노드는 n2이다.
    static int[] Level = new int[10001]; // level of root node = 0

    private static int getLevel(int n1) {
        int cnt = 0;
        while (true) {
            if (Parent[n1] == n1) break;
            n1 = Parent[n1];
            cnt++;
        }
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < t; tc++) {
            int n = Integer.parseInt(br.readLine());
            for (int i = 1; i <= n; i++) { // 초기화
                Level[i] = 0;
                Parent[i] = i;
            }
            StringTokenizer st;
            // 부모-자식관계 a, b 입력
            for (int i = 0; i < n - 1; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                Parent[b] = a;
            }
            
            // 공통 조상을 찾으려는 두 노드 x, y의 입력
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            for (int i = 1; i <= n; i++) {
                Level[i] = getLevel(i);
            }
            
            // x, y 두 노드의 레벨을 같게 해준다.
            while (true) {
                if (Level[x] == Level[y]) {
                    break;
                } else if (Level[x] < Level[y]) {
                    y = Parent[y];
                } else {
                    x = Parent[x];
                }
            }
            // 레벨이 같은 두 노드 x, y의 부모를 찾는다.
            // 두 노드는 레벨이 같으므로, 하나의 iteration마다 부모노드로 올라가면 결국 만나게 되어있다.
            while (true) {
                if (x == y) {
                    bw.write(x + "\\n");
                    break;
                }
                x = Parent[x];
                y = Parent[y];
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

사족

자바의 빠른 입출력이 익숙지 않아서 너무 오래걸렸다 ㅠㅠ

그리고 너무 코드가 장황하다… 보기 밉다

어려워잉