Q. 3584 자바 : 가장 가까운 공통 조상

Q. 3584 자바 : 가장 가까운 공통 조상

 

문제 : boj.kr/3584

골드 4 난이도의 문제이다.

 

트리의 정점의 수와 간선이 주어진다.

이후 두 정점이 주어지면 공통조상 정점을 출력하는 문제이다.

주의해야 할 점은 루트 노드는 1번 정점이 아니라는 점 이다.

 

아래와 같은 풀이로 풀었다.

1. Tree class를 만든다. 트리 클래스는 인덱스, 깊이, 자식, 부모의 정보를 가진다.

(루트 노드가 1번 정점이 아니므로  1번 정점의 부모가 null일 때 까지 정점을 이동시키고 dfs를 통해 깊이를 저장했다.)

2. 두 정점이 주어졌을 때 공통 조상을 찾기 위해 깊이를 동일하게 맞춘다.

3. 이후 한 칸씩 부모로 올라가며 공통 조상이 나올 때 까지 반복한다.

(풀고나서 다른 풀이를 찾아보니 좀 비효율적으로 푼 것 같다..)

그리고 공통 조상 탐색 알고리즘인 lca 알고리즘이 있지만,

기억이 잘 안났고 시간복잡도도 문제 없을 것 같아 적은 방식대로 풀었다.

 

시간 복잡도는 N의 크기가 최대 10,000이고

만약 두 정점이 양 쪽 끝에 있는 경우(두 정점이 ㅅ 모양의 양 끝 정점인 경우)

공통 조상은 루트 노드가 되고 최악의 시간복잡도를 가진다.

 

시간복잡도를 계산하면

깊이를 계산하기 위한 dfs - O(log N)

공통 조상 계산 - O(2 * N log N)이 된다.

따라서 시간복잡도는 약 O(N log N)이므로 시간초과는 걱정하지 않아도 된다.

 

아래와 같이 풀었다.

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

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

    static int n, v1, v2;
    static Tree[] trees;

    static class Tree{
        int depth = 0, idx = 0;
        List<Tree> child;
        Tree parent;
        Tree() {
            child = new ArrayList<>();
        }
    }
    static void input() {

        n = scan.nextInt();
        trees = new Tree[n + 1];
        for (int i = 1; i <= n; i++) {
            trees[i] = new Tree();
            trees[i].idx = i;
        }
        for (int i = 1; i < n; i++) {
            int v1 = scan.nextInt();
            int v2 = scan.nextInt();
            trees[v1].child.add(trees[v2]);
            trees[v2].parent = trees[v1];
        }

        v1 = scan.nextInt();
        v2 = scan.nextInt();
    }

    static void lca() {

        Tree v1Tree = trees[v1];
        Tree v2Tree = trees[v2];
        if (v1Tree.depth > v2Tree.depth) {
            while (v1Tree.depth != v2Tree.depth) {
                v1Tree = v1Tree.parent;
            }
        }else if (v1Tree.depth < v2Tree.depth) {
            while (v1Tree.depth != v2Tree.depth) {
                v2Tree = v2Tree.parent;
            }
        }
        while (v1Tree != v2Tree) {
            v1Tree = v1Tree.parent;
            v2Tree = v2Tree.parent;
        }
        System.out.println(v1Tree.idx);
    }

    static void calDepth(Tree tree, int depth) {

        tree.depth = depth;
        for (Tree t: tree.child) {
            calDepth(t, depth + 1);
        }
    }

    static void pro() {

        Tree tree = trees[1];
        while (tree.parent != null) tree = tree.parent;
        calDepth(tree, 0);
        lcs();
    }

    public static void main(String[] args) {

        for (int i = scan.nextInt(); i > 0; i--) {
            input();
            pro();
        }
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}