[백준] 알고리즘 분류(트리,JAVA)3584번, 가장 가까운 공통 조상

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 루트 노드가 존재하는 트리가 주어집니다.

2. 주어지는 두 노드에 대하여 가장 가까운 공통 조상 노드를 결과로 출력합니다.

3. 노드는 N-1번까지 주어집니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 트리를 구성하면서 각 부모 노드와 깊이를 구한 뒤 LCA를 진행합니다.

 

3. LCA로 얻은 결과를 출력합니다.

 

LCA(최소 공통 조상 노드 구하기).

 

[백준] 알고리즘 분류(트리,JAVA)11437번, LCA

 

위 링크에서는 각 깊이를 맞춘 뒤 깊이를 1칸씩 올리면서 탐색하지만 트리의 크기가 커진다면 "시간 초과"가 발생할 확률이 높습니다.

 

이 문제에서는 위와 같은 방법을 사용해도 해결하는 데에는 문제가 없습니다.

[백준] 알고리즘 분류(트리,JAVA)11438번, LCA 2

위 링크에서는 각 깊이를 맞출 때와 올라가면서 최소 공통 조상을 찾을 때 메모이제이션과 이분 탐색을 이용하여 기존 방법보다 시간적인 부분에서 효율적입니다.

 

저는 최소 공통 조상 문제를 풀 때에 이 방법을 주로 사용하며 이번 문제에서도 이 방법을 사용하였습니다.

 

루트 노드 구하기.

 

문제에서는 루트 노드가 존재하는 트리이지만 어떤 노드가 루트 노드인지 가르쳐주지 않습니다.

 

루트 노드의 특성 중 부모 노드가 존재하지 않는 것으로 트리를 구성할 때

 

Boolean[]배열을 이용하여 부모 노드가 없는 노드를 확인하여 루트 노드로 설정하실 수 있습니다. 

 

아래와 같은 트리일 때

4번 노드의 부모 노드 : 3

3번 노드의 부모 노드 : 1

2번 노드의 부모 노드 : 1

1번 노드의 부모 노드 : X

 

루트 노드 : 1번 노드

 

예제입력 1.

※테스트 케이스 2번을 진행하는 과정만 보여드리겠습니다.

 

1. 입력된 정보를 저장합니다.

 

N : 5

 

2 3

3 4

3 1

1 5

 

2. 트리를 구성하면서 각 부모 노드와 깊이를 구한 뒤 LCA를 진행합니다.

 

트리를 구성.

깊이와 부모 노드 관련 배열 설정.

 

메모이제이션의 값들도 정의를 진행합니다.

parent[5][1] = 2¹위에 있는 부모 노드 : 3

parent[5][2] = 2²위에는 부모 노드 존재 X

....

 

최소 공통 조상 노드를 찾아야 할 두 노드 : 3 5

 

노드 3과 노드 5에 깊이를 맞추기.

두 노드의 깊이를 맞추면 같은 노드에 도달합니다.(3번 노드)

 

깊이를 맞추었을 때 같은 노드이면 해당 노드가 최소 공통 조상노드가 됩니다.

 

3. LCA로 얻은 결과를 출력합니다.

 

최소 공통 조상 노드 : 3번 노드

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리의 노드 정보를 띄어쓰기 기준 나누었습니다.
• getHeght으로 얻은 트리에 대한 최대 깊이를 이용하여 배열을 구성하였습니다.
• getRoot으로 얻은 루트 노드 기준으로 setDepth 실행하여 트리의 깊이와 부모 노드를 설정하였습니다.
• setParent으로 부모 노드에 대한 메모이제이션을 구성합니다.
• 최소 공통 조상 노드를 찾는 두 노드에 대하여 LCA를 진행한 결과를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• getHeight함수는 트리의 최대 높이를 구합니다.
• getRoot함수는 트리의 루트 노드를 구합니다.
• setDepth함수는 각 노드의 깊이와 부모 노드를 저장합니다.
• setParent함수는 부모 노드의 메모이제이션 값들을 구성합니다.
• LCA함수는 두 노드의 최소 공통 조상 노드를 구합니다.
• LCA함수는 a의 깊이가 더 깊다고 가정하고 진행합니다.
• LCA함수는 깊이를 맞출 때와 올라갈 때 이분 탐색을 이용합니다.

 

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


public class Main {
    static int[][] parent;	//부모 노드 관련 메모이제이션 배열
    static int[] depth;		//깊이 관련 배열
    static boolean[] check;	//루트 노드 관련 배열
    static ArrayList<ArrayList<Integer>> tree;	//트리 관련 저장 리스트
    static int size, root;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        //각 테스트 케이스 진행.
        for(int i=0;i<T;i++){
            int N = Integer.parseInt(br.readLine());
            tree = new ArrayList<>();
            check = new boolean[N+1];
            depth = new int[N+1];
            size = getHeight(N);
            parent = new int[N+1][size];
            for(int j=0;j<=N;j++)
                tree.add(new ArrayList<>());
            //트리 정보 저장.
            for(int j=1;j<N;j++){
                st = new StringTokenizer(br.readLine()," ");
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                tree.get(A).add(B);
                tree.get(B).add(A);
                check[B] = true;	//B의 부모 노드 존재.
            }
            getRoot(N);		//루트 노드 구하기
            setDepth(1, root, 0);	//트리의 깊이 및 부모 노드 구하기
            setParent(N);	//Parent[][] 메모이제이션 배열 구성
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bw.write(LCA(a, b) + "\n");		//LCA 결과 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //트리의 최대 높이 구하는 함수
    static int getHeight(int n){
        return (int)Math.ceil(Math.log(n) / Math.log(2)) + 1;
    }
    //트리의 루트 노드 구하는 함수
    static void getRoot(int n){
        for(int i=1;i<=n;i++){
            if(!check[i]){
                root = i;
                return;
            }
        }
    }
    //트리의 깊이와 부모 노드 구성하는 함수
    static void setDepth(int d, int cur, int p){
        depth[cur] = d;
        for(int next : tree.get(cur)){
            if(p != next){
                parent[next][0] = cur;
                setDepth(d+1, next, cur);
            }
        }
    }
    //Parent[][] 메모이제이션 구성하는 함수
    static void setParent(int n){
        for(int i=1;i<size;i++){
            for(int j=1;j<=n;j++){
                parent[j][i] = parent[parent[j][i-1]][i-1];
            }
        }
    }
    //LCA 진행하는 함수
    static int LCA(int a, int b){
        int da = depth[a];
        int db = depth[b];
        //da가 항상 깊이가 높다고 가정하였습니다.
        if(db > da){
            int temp = b;
            b = a;
            a = temp;
        }
        //이분 탐색으로 깊이 맞추기.
        for(int i = size-1;i>=0;i--){
            if(depth[a] - Math.pow(2, i) >= depth[b])
                a = parent[a][i];
        }
        //깊이를 맞추었을 때 같은 노드일 때는 해당 노드 최소 공통 조상 노드
        if(a==b)
            return a;
        //이분 탐색으로 깊이를 맞춘 두 노드를 올라가기 진행!
        for(int i=size-1;i>=0;i--){
            if(parent[a][i] != parent[b][i]){
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];	//최소 공통 조상 노드 반환
    }

}