공통조상찾기

포인트: 가장 가까운 공통 부모를 찾는것

문제

---

트리의 노드 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

처음 풀이 소스

import java.util.Scanner;
public class Main{
    
    public static int[] arr = new int[1001];
    public static void main(String[] args){

       // Please Enter Your Code Here
      Scanner scan = new Scanner(System.in);
      
      int n = scan.nextInt();
      int x = scan.nextInt();
      int y = scan.nextInt();
      
      for(int i=0;i<(n-1);i++)
      {
        int a = scan.nextInt();
        int b = scan.nextInt();
        arr[b]=a;
      }
      
      int xIdx=0;
      int[] xArr = new int[1001];
      int tempX = x;
      while(arr[tempX]!=0)
      {
        xArr[xIdx++]=arr[tempX];
        tempX=arr[tempX];
      }
      // for(int i=0;i<=xIdx;i++)
      // {
      //   System.out.print(xArr[i]+" ");
      // }System.out.println();
      
      int yIdx=0;
      int[] yArr = new int[1001];
      int tempY = y;
      while(arr[tempY]!=0)
      {
        yArr[yIdx++]=arr[tempY];
        tempY=arr[tempY];
      }
      // for(int i=0;i<=yIdx;i++)
      // {
      //   System.out.print(yArr[i]+" ");
      // }System.out.println();
      
      boolean flag = true;
      int ans=0;
      for(int i=0;i<xIdx;i++)
      {
        int target = xArr[i];
        // System.out.println("target:"+target);
        
        for(int j=0;j<yIdx;j++)
        {
          if(target==yArr[j])
          {
            ans = target;
            flag = false;
            break;
          }
        }
        if(!flag)break;
      }
      System.out.println(ans);      
      
      
      
      scan.close();
    }
}

 

 

 

 

다른 접근방식

개선된 소스

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static int n,first,second;
    public static int[] arr;
    public static boolean[] av;
    public static void main(String[] args){

      Scanner scan = new Scanner(System.in);
      input(scan);
      getAnswer();
      scan.close();
    }
    
    public static void getAnswer()
    {
      int temp = first;
      
      while(true)
      {
        temp = arr[temp];//올라가고
        av[temp]=true;//칠하고
        if(temp==0)break;
      }
      // System.out.println(Arrays.toString(av));
      temp = second;
      while(true)
      {
        //올라가고 체크하고
        temp = arr[temp];
        if(av[temp]){System.out.println(temp);return;}
      }
    }
    public static void input(Scanner scan)
    {
      n = scan.nextInt();first = scan.nextInt();second = scan.nextInt();
      arr = new int[n];av = new boolean[n];
      for(int i=0;i<n-1;i++)
      {
        int a = scan.nextInt();
        int b = scan.nextInt();
        arr[b]=a;
      }
      // System.out.println(Arrays.toString(arr));
    }
}