[백준/JAVA] 11438번: LCA 2

🔺 문제

11438번: LCA 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, K;
 
    static int[] depth;
    static int[][] parent;
    
    static ArrayList<Integer>[] tree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        // 2^K > N 인 K 찾기
        K = 0;
        for(int i = 1 ; i <= N ; i *= 2) {
            K++;
        }
        
        // LCA 관련 변수 초기화
        depth  = new int[N + 1];
        parent = new int[K][N + 1];
        
        // tree 관련 변수 초기화
        tree = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            tree[i] = new ArrayList<>();
        }
        
        for(int i = 1 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            tree[s].add(e);
            tree[e].add(s);
        }
        
        // depth 확인
        DFS(1, 1);
        
        // 2^N까지 parent 채우기
        fillParent();
        
        // LCA 진행
        M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            sb.append(LCA(s, e) + "\n");
        }
        
        bw.write(sb.toString());
        
        bw.flush();
        bw.close();
        br.close();
    }
    
    // depth 확인용 DFS
    static void DFS(int node, int cnt) {
        depth[node] = cnt;
        
        for(int next : tree[node]) {
            if(depth[next] == 0) {                DFS(next, cnt + 1);
                parent[0][next] = node;    // 첫번째 부모 기록
            }
        }
    }
    
    // 부모 채우기 (2^k번째 조상 노드 저장)
    static void fillParent() {
        for(int i = 1 ; i < K ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                parent[i][j] = parent[i-1][parent[i-1][j]];
            }
        }
    }
    
    // 최소 공통 조상
    static int LCA(int a, int b) {
        // 1. depth[a] >= depth[b]가 되도록 조정
        if(depth[a] < depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        
        // 2. 더 깊은 a를 2^K승 점프해 depth !빠르게! 맞추기
        for(int i = K - 1 ; i >= 0 ; i--) {
            if(Math.pow(2, i) <= depth[a] - depth[b]) {
                a = parent[i][a];
            }
        }
        
        // 3. depth를 맞췄는데 같다면 종료
        if(a == b) return a;
        
        // 4. a,b는 같은 depth이므로 2^K승 점프해 공통부모 바로 아래까지 올리기
        for(int i = K - 1 ; i >= 0 ; i--) {
            if(parent[i][a] != parent[i][b]) {
                a = parent[i][a];
                b = parent[i][b];
            }
        }
        return parent[0][a];
    }
}

✅ 해결 아이디어
✔ LCA 빠르게 구하기! 점화식 이용
→ P[K][N] = P[K-1][P[K-1][N]]

 

과정

1) 인접 리스트로 트리 데이터 구현

2) 각 노드 깊이 계산 (탐색 알고리즘 사용)

3) 부모 노드 배열 구하기 (점화식 사용)

4) 깊이가 큰 노드는 부모 노드 배열 이용해 2^K만큼 이동시켜 깊이 맞춤

5) 부모 노드로 올라가면서 LCA 찾기 (2^K만큼 넘어가면서 찾기! K는 depth 최댓값에서 -1씩 하면서)

 

 

💥 유의사항

• 최소 공통 조상 로직 ⇨ LCA 2^N 이용 & DP적 요소

 

 

---

🔺 다른 풀이들

다들 비슷한데 parent 배열에서 i와 j의 자리를 바꿔 쓰셨다.

[JAVA/백준] 11438번: LCA 2

 

그리고 2^K > N인 최초의 K를 찾을 때 비트 시프트 연산자 <<를 사용하셨다.

int maxDepth = 0;
int K = 1;

// 트리의 깊이 계산
while(K <= N) {
    K <<= 1;
    maxDepth++;
}

 

---

💬 느낀 점

뭔지는 알겠는데 혼자 하라면 아직은 못 할 것 같아서 복습을 해야겠다!

깊이가 안 맞을 때 한 칸씩 올라가는 게 아니라 2의 제곱수씩 올라가서 빠른 LCA라고 하는 것이라함!!

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ 백준] LCA 2(11438) Java