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

문제 링크

11437번: LCA

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 트리에 대한 정보가 주어지고 두 노드의 가장 가까운 공통 조상 노드를 결과로 출력합니다.

2. 루트 노드는 항상 1번입니다.

3. 트리의 각 정점은 1번~N번까지 존재합니다.

 

알고리즘 진행 순서.

 

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

 

2. 입력된 정보로 트리 형성 및 부모 노드와 깊이를 따로 저장합니다.

 

3. M개의 노드 쌍에 대한 공통 조상 노드를 찾아서 결과로 출력합니다.

 

 

공통 조상 노드 찾기!

 

1. 두 노드의 깊이가 다르면 같도록 바꾼다.

 

2. 깊이가 같아지면 부모 노드로 동시에 1칸씩 이동하며 같은 노드를 가리킬 때까지 반복합니다.

 

3. 같은 노드를 가리킬 때까 최소 공통 조상 노드로써 결과로 출력합니다.

 

최소 공통 조상 : 1번 노드

 

 

예제입력 1.

테스트케이스 1.

 

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

 

N : 15

노드 연결 쌍 : (1, 2), (1, 3), (2, 4), (3, 7), (6, 2), (3, 8), (4, 9), (2, 5), (5, 11), (7, 13), (10, 4), (11, 15), (12, 5), (14, 7)

M : 6
최소 공통 조상 노드 찾아야 할 쌍 : (6, 11), (10, 9), (2, 6), (7, 6), (8, 13), (8, 15)

 

2. 입력된 정보로 트리 형성 및 부모 노드와 깊이를 따로 저장합니다.

부모 노드는 배열로 따로 저장하였습니다.

parent[15] = 11, parent[2] = 1.....

 

노드의 깊이도 배열로 따로 저장하였습니다.

depth[15] = 5, depth[2] = 2.....

 

3. M개의 노드 쌍에 대한 공통 조상 노드를 찾아서 결과로 출력합니다.

※1번째 노드의 쌍만 공통 조상 노드를 구하는 과정을 보여드리겠습니다.

 

(6, 11)

 

1) 두 노드의 깊이가 다르면 같도록 바꾼다.

 

depth[6] = 3

depth[11] = 4

다르기 때문에 깊이가 큰 11의 노드를 같아지도록 바꿉니다.

 

 

2) 깊이가 같아지면 부모 노드로 동시에 1칸씩 이동하며 같은 노드를 가리킬 때까지 반복합니다.

3) 같은 노드를 가리킬 때까 최소 공통 조상 노드로써 결과로 출력합니다.

 

최소 공통 조상 노드 : 2를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 노드의 관계를 띄어쓰기 기준 나누었습니다.
• 노드 간 관계를 저장한 뒤 부모 노드, 깊이 및 트리를 형성하는 setTree함수를 실행하였습니다.
• M개의 노드 쌍에 대한 LCA함수를 실행하여 최소 공통 조상 노드를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• setTree함수는 각 노드의 관계를 이용해서 부모 노드, 깊이 및 트리를 형성하는 재귀 함수입니다.
• LCA함수는 각 노드의 깊이와 부모 노드를 이용해서 최소 공통 조상 노드를 구하는 함수입니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
    static int[] parent, depth;	//부모 노드와 깊이 저장하는 배열
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();	//트리 형성 리스트
    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 N = Integer.parseInt(br.readLine());
        parent = new int[N+1];
        depth = new int[N+1];
        for(int i=0;i<=N;i++)
            tree.add(new ArrayList<>());
        //트리에 대한 정보로 노드간 관계 만들기
        for(int i=1;i<N;i++){
            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);
        }
        setTree(1, 1, 0);	//트리 만들기

        int M = Integer.parseInt(br.readLine());
        //M개의 노드 쌍 최소 공통 조상 노드 탐색 및 결과 BufferedWriter 저장
        for(int i=0;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();
    }
    //트리를 형성 및 부모 노드와 깊이 저장하는 재귀함수
    static void setTree(int cur, int d, int p){
        depth[cur] = d;		//깊이 저장
        parent[cur] = p;	//부모 노드 저장
        //자식 노드들 탐색
        for(int next : tree.get(cur)){
            if(next == p)
                continue;
            setTree(next, d+1, cur);
        }
    }
    //최소 공통 조상 노드 구하는 함수
    static int LCA(int a, int b){
        int ah = depth[a];		//a의 깊이
        int bh = depth[b];		//b의 깊이
        //a의 깊이가 b보다 클 경우 감소시키기
        while(ah > bh){
            a = parent[a];
            ah--;
        }
        //b깊이가 a보다 클 경우 감소시키기
        while(ah < bh){
            b = parent[b];
            bh--;
        }
        //깊이가 같아졌을 때 동시에 올라가면서 공통 조상 노드 찾기
        while(true){
            if(a==b)
                return a;
            a = parent[a];
            b = parent[b];
        }
    }
}