백준 - 가장 가까운 공통 조상

문제

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

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

예를 들어 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 이하의 정수로 이름 붙여집니다.

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

 

 

출력

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

 

 

풀이

먼저 트리를 구성한 뒤에, 비교를 위한 첫번째 노드의 부모 노드들을 넣어주는 리스트를 하나 만들어준 뒤, 두번째 부모 노드를 따라가면서 가장 처음으로 리스트 안의 노드와 만나게 되면 해당 노드를 출력해 주는 식으로 풀어보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder bd = new StringBuilder();
        int cnt = Integer.parseInt(br.readLine());
        for (int c = 0; c < cnt; c++) {
            int nodes = Integer.parseInt(br.readLine());
            int[] parentsTable = new int[nodes + 1];
            StringTokenizer st;

            for (int i = 1; i < parentsTable.length-1; i++) {
                st = new StringTokenizer(br.readLine());
                int parents = Integer.parseInt(st.nextToken());
                int child = Integer.parseInt(st.nextToken());
                parentsTable[child] = parents;
            }
            st = new StringTokenizer(br.readLine());
            int findOne = Integer.parseInt(st.nextToken());
            int findTwo = Integer.parseInt(st.nextToken());
            bd.append(findParentsNode(findOne, findTwo, parentsTable)).append("\n");
        }
        System.out.println(bd);
    }

    private static int findParentsNode(int findOne, int findTwo, int[] parentsTable) {
        ArrayList<Integer> parentList = new ArrayList<>();
        int parent = findOne;
        parentList.add(parent);
        while (parent != 0){
            parent = parentsTable[parent];
            parentList.add(parent);
        }

       parent = findTwo;
        while (!parentList.contains(parent)){
            parent = parentsTable[parent];
        }
        return parent;
    }

}

 

각 배열에 자식노드와 1대1로 매칭되는 부모노드를 넣어주어(인덱스는 자식노드, 값은 부모 노드가 되도록) 쉽게 부모노드를 찾아갈 수 있도록 하였다. (값이 0일 경우 더 이상의 부모 노드가 없으므로, while문 중료)

 

에러 핸들링

처음 findOne 노드를 넣고 시작해야 한다. ( 비교하려는 첫 번째 노드가 두 번째 노드와 가장 먼저 만나는 노드일 수도 있기 때문)