95. 가장 가까운 공통 조상 (백준 3584) [JAVA]

 

문제

문제 링크 : https://www.acmicpc.net/problem/3584

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

문제

루트가 있는 트리(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 이하의 정수로 이름 붙여집니다.

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

출력

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

 

 

풀이

가장 깊은 길이의 공통 부모를 쉽게 찾는 방법은, 자식으로부터 역행하면 된다. (Bottom-Up)

따라서 굳이 나의 자식노드들은 기억할 필요 없이, 부모만 저장하고 역으로 올라가는 방식을 사용하면 된다.

두 노드중에 한명의 부모를(본인 포함) 쭉 구한 다음에

그 다음 노드에서 하나씩 부모로 올라가면서 찾으면 된다.

 

 

코드

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

public class Main {

    static int T;
    //노드 수
    static int N;
    static int targetA, targetB;
    static ArrayList<Integer> parentList;
    static HashMap<Integer, Integer> nodes;
    static ArrayList<Integer> answerList = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

            T = Integer.parseInt(br.readLine());
            int parent, child;

            for(int i=0; i<T; i++) {
                N = Integer.parseInt(br.readLine());
                nodes = new HashMap<Integer, Integer>();
                parentList = new ArrayList<Integer>();

                for(int j=0; j<N-1; j++) {
                    st = new StringTokenizer(br.readLine());
                    parent = Integer.parseInt(st.nextToken());
                    child = Integer.parseInt(st.nextToken());

                    if(!nodes.containsKey(parent)) {
                        nodes.put(parent, -1);
                    }

                    if(!nodes.containsKey(child)) {
                        nodes.put(child, parent);
                    }
                    else {
                        nodes.replace(child, -1, parent);
                    }
                }

                //구해야 할 애들
                st = new StringTokenizer(br.readLine());
                targetA = Integer.parseInt(st.nextToken());
                targetB = Integer.parseInt(st.nextToken());
                GetParent(targetA);
                CompareParent(targetB);
            }

            //정답 출력
            for(int s : answerList) {
                System.out.println(s);
            }
    }

    public static void GetParent(int A) {
        parentList.add(A);
        int parentA = nodes.get(A);
        if(parentA != -1) {
            GetParent(parentA);
        }
    }

    public static void CompareParent(int B) {
        if(parentList.contains(B)) {
            answerList.add(B);
            return;
        }
        CompareParent(nodes.get(B));
    }
}

 

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!