공통 조상

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AV15PTkqAPYCFAYD&categoryType=CODE&&&

SW Expert Academy

 

알고리즘

1. 배열의 인덱스가 자식 값이 부모 형태로 저장한다.

 

2. 재귀를 통해서 두 수를 만족하는 부모를 찾는다.

 

3. 부모를 찾으면 BFS를 이용하여 자식의 개수를 count 한다.

 

주의사항

1. 푸는 방법에 따라 쉬워질 수도 있고 어려워질 수도 있다.

 

구현

class Solution
{
    static int arr[];
    static int root[];
    static int result;
    static int V;
    static int index;
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            V = Integer.parseInt(s.nextToken()); //정점 개수
            int E = Integer.parseInt(s.nextToken()); //간선 개수
            int N = Integer.parseInt(s.nextToken()); //두정점
            int M = Integer.parseInt(s.nextToken());
            result = 0;
            arr = new int[V+1];
            root = new int[V];
            s = new StringTokenizer(in.readLine()," ");
            for (int i = 0; i < E; i++) {
                int a = Integer.parseInt(s.nextToken());
                int b = Integer.parseInt(s.nextToken());
                arr[b] =a;
            }
            LinkedList<Integer> queue = new LinkedList<Integer>();
            DFS(N,0);
            DFS(M,0);
            if(result == 0)
                result = 1;
            int count=1; //result 포함
            for (int i = 1; i < V+1; i++) {
                if(result == arr[i])
                {
                    queue.offer(i);
                    count++;
                }
            }
            while(!queue.isEmpty())
            {
                int temp = queue.poll();
                for (int i = 1; i < V+1; i++) {
                    if(temp == arr[i])
                    {
                        queue.offer(i);
                        count++;
                    }
                }
            }
            System.out.println("#"+test_case+" "+result+" "+count);
        }
    }
    private static void DFS(int n, int cnt) {
        if(n == 0)
        {
            index = cnt;
            return;
        }
        else if(root[cnt] == 0)
            root[cnt] = n;
        else
        {
            for (int i = 0; i < index; i++) {
                if(n == root[i])
                {
                    result = n;
                    return;
                }
            }
        }
        DFS(arr[n],cnt+1);
    }        
}