[G4] 가장 가까운 공통 조상 : Java : 3584 -LCA, DFS

 

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

 

 

 

 

---

문제 풀이 핵심

1. root 노드를 찾기
2. 가장 가까운 공통 노드 찾기

 

 

root 노드 찾기

 root 노드를 찾기 위해 입력 자식 노드를 체크 해준다. 그리고 입력이 끝난 후에 체크되지 않은 노드가 root 노드이다.

 

 

 

 

가장 가까운 노드 찾기

LCA(Lowest Common Ancestor) 알고리즘을 이용한다!   LCA 알고리즘의 핵심 순서는 3가지이다. 

1. 각 노드의 Depth, Parent 리스트를 구한다. Depth는 해당 노드의 깊이를, Parent는 해당 노드의 부모 노드 값을 나타낸다.
2. 공통 조상을 구할 두 노드의 Depth를 같도록 맞춘다.
3. 부모를 타고 올라가면서 같은 부모 값이 나오면 그만둔다.

트리를 타고 올라가므로 시간 복잡도는 O(logn)이다.  1번 과정의 Depth와 Parent를 구할 때는 DFS 방법을 이용한다. 

 

static void init(int idx, int d, int p){
        parent[idx] = p;
        depth[idx] = d;
        for(int next : tree[idx]){
            if(next != p){
                init(next, d+1 , idx);
            }
        }
    }

 

 

 

 

 

 

LCA 코드

 static int LCA(int a, int b){
        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;
    }

 

 

 

 

 

 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static List<Integer>[] tree;
    static int [] parent, depth;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while(T>0){
            T--;
            int n = Integer.parseInt(br.readLine());

            parent = new int[n+1];
            depth = new int[n+1];
            tree = new ArrayList[n+1];

            // 초기화
            for(int i=1; i<= n; i++){
                tree[i] = new ArrayList<Integer>();
            }

            boolean [] isRoots = new boolean[n+1];
            Arrays.fill(isRoots, true);
            // 트리 완성
            for(int i=0; i< n-1; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int parent = Integer.parseInt(st.nextToken());
                int child = Integer.parseInt(st.nextToken());
                tree[parent].add(child);
                isRoots[child] = false;
            }

            int root = 0;
            for(int i=1; i<isRoots.length; i++){
                if(isRoots[i]){
                    root = i;
                    break;
                }
            }

            init(root, 1, 0);
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            System.out.println(LCA(x1,x2));

        }


    }

    static void init(int idx, int d, int p){
        parent[idx] = p;
        depth[idx] = d;
        for(int next : tree[idx]){
            if(next != p){ // 이 조건은 어떤 경우지? 양방향?
                init(next, d+1 , idx);
            }
        }
    }

    static int LCA(int a, int b){
        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;
    }

}