[Platinum V] LCA 2 - 11438

문제 링크

성능 요약

메모리: 108964 KB, 시간: 952 ms

분류

자료 구조, 최소 공통 조상, 희소 배열, 트리

제출 일자

2025년 4월 16일 23:37:54

문제 설명

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

문제 풀이

• 트리에 대한 정보가 주어지고 두 노드의 가장 가까운 공통 조상 노드를 결과로 출력
• 루트 노드는 항상 1번
• 트리의 각 정점은 1번~N번까지 존재

1. 입력된 트리의 정보를 저장
2. 입력된 정보로 트리 형성 및 부모 노드(DP)와 깊이를 따로 저장
3. M개의 노드 쌍에 대한 공통 조상 노드를 찾아서 결과로 출력

DP 구성하기 (희소 배열)

조상 노드에 대한 메모이제이션으로 dp[][]를 구성

• dp[m][n] = m번 노드의 2ⁿ만큼 위에 있는 부모 노드를 가리킴

• 점화식 : dp[m][n] = dp[dp[m][n-1]][n-1]

공통 조상 노드 구하기

• 두 노드의 깊이가 다르면 깊이가 같아지도록 맞춤

• 이진 탐색(희소 배열)을 이용해 탐색 횟수를 줄임

• 깊이가 같아지면 부모 노드로 동시에 이동하며 같은 노드를 가리킬 때까지 반복

코드

/**
  * Author: nowalex322, Kim HyeonJae
  */
 
 import java.io.*;
 import java.util.*;
 
 public class Main {
     static BufferedReader br;
     static BufferedWriter bw;
     static StringTokenizer st;
     static int N, M, maxH;
     static int[] depth;
     static int[][] dp;
     static ArrayList<Integer>[] tree;
     public static void main(String[] args) throws Exception {
         new Main().solution();
     }
 
     public void solution() throws Exception {
         br = new BufferedReader(new InputStreamReader(System.in));
 //        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_11438_LCA2/input.txt")));
         bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
         N = Integer.parseInt(br.readLine());
 
         // 트리의 maxH
         for(int i=1; i<=N; i*=2){
             maxH++;
         }
 
         dp = new int[N+1][maxH];
         depth = new int[N+1];
 
         tree = new ArrayList[N+1];
         for(int i=0; i<=N; i++){
             tree[i] = new ArrayList<>();
         }
 
         for(int i=1; i<N; i++){
             st = new StringTokenizer(br.readLine());
             int u = Integer.parseInt(st.nextToken());
             int v = Integer.parseInt(st.nextToken());
             tree[u].add(v);
             tree[v].add(u);
         }
 
         initTree(1, 1, 0);
         initParent();
 
         M = Integer.parseInt(br.readLine());
         for(int i=1; i<=M; i++){
             st = new StringTokenizer(br.readLine());
             int a = Integer.parseInt(st.nextToken());
             int b = Integer.parseInt(st.nextToken());
             bw.write(LCA(a, b) + "\n");
         }
 
         bw.flush();
         bw.close();
         br.close();
     }
 
     private static int LCA(int a, int b) {
         int a_h = depth[a];
         int b_h = depth[b];
 
         // a높이 항상 크게 유지
         if(a_h < b_h){
             int tmp = a;
             a = b;
             b = tmp;
         }
 
         //같은 높이에서 시작하게 높이 맞추기
         for(int i=maxH-1; i>=0; i--){
             a_h = depth[a];
             b_h = depth[b];
             int depthGap = a_h - b_h;
 
             if(Math.pow(2, i) <= depthGap) a = dp[a][i]; //희소 배열처럼 점프
         }
 
         if(a==b) return a;
 
         // 같은 부모 가리킬때까지 위로 진행 (같은 높이)
         for(int i=maxH-1; i>=0; i--){
             if(dp[a][i] != dp[b][i]){
                 a = dp[a][i];
                 b = dp[b][i];
             }
         }
 
         return dp[a][0];
     }
 
     private void initParent() { // dp(부모저장2차원배열) 점화식
         for(int h=1; h<maxH; h++){
             for(int node=1; node<=N; node++){
                 dp[node][h] = dp[dp[node][h-1]][h-1]; // node의 2^h번째 부모 = (node의 부모)의 2^(h-1)번째 부모
             }
         }
     }
 
     private static void initTree(int child, int parent, int d) { // 재귀적으로 아래로 내려가며 트리 형태 만들기
         depth[child] = d;
         dp[child][0] = parent;
         for(int next : tree[child]){
             if(next == parent) continue;
             initTree(next, child, d+1);
         }
     }
 
 
 }