[BOJ 3584번] 가장 가까운 공통 조상 Tree 구조에서 찾아보기- Java

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

---

풀이 순서는 아래와 같다.

1. parent의 여부를 배열에 저장하며 parent가 없는 root 노드를 직접 찾는다.

2. 각 노드의 parent node를 parent[]에 저장해놓는다.

3. 입력받은 두 노드에 대해 parent 배열을 활용하여 root까지 거슬러 올라가면서 depth를 찾는다.

4. 이후 공통 조상은 같은 depth에 있는 노드이므로, 먼저 두 노드의 depth를 맞추어주고, 부모 노드가 같아질 때까지 계속 위로 거슬러 올라간다. 

 

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

public class Main{
    static int parent[];
    static int root;
    static int depth(int a){
        int count=0;
        while(a!=root){
            a=parent[a];
            count++;
        }
        return count;
    }
    static int find(int first_depth, int second_depth, int a, int b){
         //두 노드의 depth가 다를 경우 낮은 depth의 노드의 높이를 올려 depth를 맞추어줌
          while (first_depth>second_depth){
            first_depth--;
            a=parent[a];  
          }
         while (first_depth<second_depth){
            second_depth--;
            b=parent[b];  
          }
          //같은 depth에서 시작하여 공통 parent node가 나올때까지 타고 올라감
         while(a!=b){
             a=parent[a];
             b=parent[b];
         }
        return a;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       
        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            int n=Integer.parseInt(br.readLine());
            parent=new int [n+1];
            boolean child[]=new boolean[n+1]; //root인지 child인지 판별
            for(int i=0; i<n-1; i++){
              String infos[]=br.readLine().split(" ");
              parent[Integer.parseInt(infos[1])]=Integer.parseInt(infos[0]);
              child[Integer.parseInt(infos[1])]=true;
            }
            //root 찾는 과정
            //root는 parent가 없는 node이므로 child 배열이 false이다. 
            for(int i=1; i<=n; i++){
                if (!child[i]){
                    root=i;
                    break;
                }
            }
            String test[]=br.readLine().split(" ");
            int a=Integer.parseInt(test[0]);
            int b=Integer.parseInt(test[1]);
            //두 노드에 대한 depth를 찾아줌
            int first_depth=depth(a);
            int second_depth=depth(b);
            System.out.println(find(first_depth, second_depth, a, b));
        }
    }
}

여기서는 parent node를 사용하여 depth를 구해주었지만 상황에 따라 BFS 등을 활용하여 depth를 구하는 방법도 있다.

방법은 정해진 것이 아니므로 여러가지로 시도해보자.