[백준 Gold 4] 3584 가장 가까운 공통 조상 - Java

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

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

 

접근 과정 : 

• 부모 - 자식 관계가 주어지고 두 노드가 주어졌을 때, 그 두 노드의 가장 가까운 공통 조상을 찾으면 된다.
• 저장한 부모-자식 관계를 따라서 노드 A의 조상을 체크한다.
• DFS로 B의 조상을 탐색하면서 A의 조상체크가 되어있는 조상을 발견하면 리턴한다.

 

 

소스 코드 및 결과 :

package BOJ;

/* 
    가장 가까운 공통 조상
*/

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

public class BOJ3584 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] parent = new int[N + 1];

            for (int i = 1; i < N; i++) {
                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                parent[b] = a;
            }

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            boolean[] isParent = new boolean[N + 1];
            while (a != 0) {
                isParent[a] = true;
                a = parent[a];
            }

            while (true) {
                if (isParent[b]) {
                    sb.append(b).append("\n");
                    break;
                }

                b = parent[b];
            }

        }

        System.out.println(sb.toString().trim());

    }

}

 

P.S 

확인해야 할 관계가 하나만 있기에, LCA 알고리즘 없이도 풀 수 있었다..

근데. LCA 어렵...