[JAVA] 백준 11437 LCA

 

 

 

 

 

 

11437번: LCA

LCA란?

[Algorithm] 최소 공통 조상 LCA란?

문제

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

풀이

두 노드가 주어졌을 때 가까운 공통 조상이 몇번인지 출력하기 위해 LCA 알고리즘을 사용하여 문제를 해결하였습니다.

📌 입력

        for(int i=1; i<N-1; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[a].add(b);
            A[b].add(a);
        }

BFS 알고리즘을 통해 트리의 깊이와 부모 노드를 계산해야 합니다.

따라서 인접 리스트 형태로 트리를 표현해주었습니다.

📌 BFS

    static void BFS(int a){
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    q.add(x);
                    V[x] = true;
                    D[0][x] = now;
                    D[1][x] = D[1][now] +1;
                }
            }
        }
    }

BFS 알고리즘으로 모든 노드를 돌면서 D[0][x]에는 부모 노드가 D[1][x]에는 깊이를 저장했습니다.

📌 LCA

    public static int LCA(int a, int b){
        if(D[1][a] > D[1][b]){
            int temp = b;
            b = a;
            a = temp;
        }
        while (D[1][a] != D[1][b]){
            b = D[0][b];
        }
        while (a != b){
            a = D[0][a];
            b = D[0][b];
        }
        return a;
    }

• D[1][a] > D[1][b]를 비교하여 무조건 b에 깊이가 더 깊은 노드가 오도록 했습니다.
• while(D[1][a] ≠ D[1][b])를 반복하면서 b를 부모 노드로 한단계씩 올라갑니다. 이때 a와 b의 깊이가 같아질 때 까지 진행합니다.
• while(a ≠ b) 깊이가 같을 때, a와 b의 값이 같을 때 까지 반복해서 최소 공통 조상을 찾아냅니다.

📌 전체 코드

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

class Main {
    static int[][] D;
    static boolean[] V;
    static ArrayList<Integer>[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+1;

        V = new boolean[N];
        D = new int[2][N];
        A = new ArrayList[N];
        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for(int i=1; i<N-1; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[a].add(b);
            A[b].add(a);
        }
        BFS(1);

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a= Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(LCA(a, b)).append("\n");
        }
        System.out.println(sb);

    }

    static void BFS(int a){
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    q.add(x);
                    V[x] = true;
                    D[0][x] = now;
                    D[1][x] = D[1][now] +1;
                }
            }
        }
    }

    public static int LCA(int a, int b){
        if(D[1][a] > D[1][b]){
            int temp = b;
            b = a;
            a = temp;
        }
        while (D[1][a] != D[1][b]){
            b = D[0][b];
        }
        while (a != b){
            a = D[0][a];
            b = D[0][b];
        }
        return a;
    }
}

결과