[필수 문제] 공통 조상 찾기

1. 문제

트리의 노드 X에 대하여 “조상"을 정의할 수 있다. X의 “조상"이란, 루트까지 올라가는 중에 만나는 모든 노드를 말한다. 예를 들어, 아래와 같이 트리가 주어질 경우, 노드 8의 “조상"은 노드 0, 노드 2, 노드 6이 된다.

두 노드 X, Y의 공통 조상이란, X와 Y가 공통으로 갖는 조상을 말한다. 예를 들어, 노드 7과 노드 10의 공통조상은 노드 2, 노드 0이 된다. 가장 가까운 공통 조상이란, X와 Y가 공통으로 갖는 조상들 중에서 X, Y와 가장 가까운 조상을 말한다. 예를 들어, 노드 7과 노드 10의 가장 가까운 공통 조상은 노드 2가 된다. 트리가 주어지고, 두 노드 X, Y가 주어질 때, 가장 가까운 공통 조상을 찾는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 트리의 노드 개수 n, 두 노드 X, Y의 번호가 주어진다. ( 1 ≤ X, Y ≤ n ≤ 1000 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 노드 a가 노드 b의 부모노드라는 것을 의미한다. 루트는 노드 0이라고 가정한다.  

출력

두 노드 X, Y의 공통 조상을 출력한다.

예제 입력

11 7 10
0 1
0 2
1 3
1 4
1 5
2 6
2 10
6 7
6 8
6 9

예제 출력

2

 

 

 

2. 풀이

이 문제는 b의 부모 a를 담는 배열을 생성하고, x의 조상을 찾아가면서 방문했음을 표시해준다. 이 후 y의 조상을 찾아가면서 이미 방문한 조상이 있을 경우, 해당 조상을 출력해주면 된다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        int[] parent = new int[n];
        boolean[] isVisited = new boolean[n];

        for(int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            parent[b] = a; // a가 b의 부모
        }

        // x의 조상
        while(true) {
            isVisited[x] = true;
            if(x == 0) break;
            x = parent[x];
        }

        // y의 조상
        while(true) {
            if(isVisited[y]) { // 가장 가까운 공통된 조상 (제일 처음 만난 공통 조상)
                bw.write(y + "");
                break;
            } else {
                isVisited[y] = true;
                y = parent[y];
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }

}