[BOJ][Java]Q3584 - 가장 가까운 공통 조상

트리 정보가 주어졌을 때, 두 정점 n1,n2의 가장 가까운 공통조상을 출력하는 문제였다.

트리 문제는 처음 풀어봐서 그래프처럼 구현해야하나 한참 생각하다가,
어차피 부모만 찾는 거라면 int배열 parent를 생성하여 각 정점의 부모만 저장해주면 될 것 같았다.

따라서 트리 정보를 입력받으며 다음과 같이 parent 배열에 부모 정보를 저장해준다.

	for(int i = 0; i<n-1;i++){
		StringTokenizer st= new StringTokenizer(br.readLine());
    	int p = Integer.parseInt(st.nextToken());	//부모
    	int c = Integer.parseInt(st.nextToken());	//자식
    	parent[c] = p;
    }

그 후 n1의 조상을 먼저 탐색하며 ArrayList parentList1에 저장하고,
n2의 조상을 탐색하며 parentList1에 들어있을 경우 출력했다.

static void findAncestor(int n1, int n2){
        //n1의 부모를 리스트에 쭉 저장한다.
        ArrayList<Integer> parentList1 = new ArrayList<>();
        int p = n1;
        while(p != 0){
            parentList1.add(p);
            p = parent[p];
        }

        //n2의 부모를 타고 올라가며, 리스트에 존재하면 출력하고 함수를 끝낸다.
        p = n2;
        while(p != 0){
            if(parentList1.contains(p)){
                System.out.println(p);
                return;
            }
            p = parent[p];
        }
    }

전체 코드

package graph_traversal.dfs;

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

public class Q3584_가장가까운공통조상 {
    /*[골드4]Q3584_가장가까운공통조상*/
    static int[] parent;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
        for(int t= 0; t<TC;t++){
            n = Integer.parseInt(br.readLine());
            parent = new int[n+1];
            for(int i = 0; i<n-1;i++){
                StringTokenizer st= new StringTokenizer(br.readLine());
                int p = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                parent[c] = p;
            }
            StringTokenizer st= new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());

            findAncestor(n1, n2);
        }
    }
    static void findAncestor(int n1, int n2){
        //n1의 부모를 리스트에 쭉 저장한다.
        ArrayList<Integer> parentList1 = new ArrayList<>();
        int p = n1;
        while(p != 0){
            parentList1.add(p);
            p = parent[p];
        }

        //n2의 부모를 타고 올라가며, 리스트에 존재하면 출력하고 함수를 끝낸다.
        p = n2;
        while(p != 0){
            if(parentList1.contains(p)){
                System.out.println(p);
                return;
            }
            p = parent[p];
        }
    }
}