공통조상찾기

가장 가까운 공통 조상 찾기

 

문제

---

트리의 노드 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.ArrayList;
import java.util.Scanner;

public class Main {

    public static ArrayList<Node> box = new ArrayList<>();
    public static ArrayList<Node> fatherBox = new ArrayList<>();
    public static ArrayList<Node> fatherBox2 = new ArrayList<>();
    public static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int b2;
        int c = 0;
        int d = 0;
        int result = 0;

        a = sc.nextInt();

        for (int i = 0; i < a; i++) {
            Node node = new Node(i);
            box.add(node);
        }

        b = sc.nextInt();
        b2 = sc.nextInt();

        for (int i = 1; i < a; i++) {
            c = sc.nextInt();
            d = sc.nextInt();
            box.get(c).getNodes().add(box.get(d));
            box.get(d).setFather(box.get(c));
        }

        Node find1 = box.get(b);
        Node find2 = box.get(b2);

        fatherBox.add(find1);
        fatherBox2.add(find2);

        while (find1.getData() != 0 || find2.getData() != 0) {
            if (find1.getData() != 0) {
                fatherBox.add(find1.getFather());
                find1 = find1.getFather();
            }
            if (find2.getData() != 0) {
                fatherBox2.add(find2.getFather());
                find2 = find2.getFather();
            }
        }

        fullFor:
        for (int i = 0; i < fatherBox.size(); i++) {
            for (int j = 0; j < fatherBox2.size(); j++) {
                if (fatherBox.get(i).getData() == fatherBox2.get(j).getData()) {
                    result = fatherBox.get(i).getData();
                    break fullFor;
                }
            }
        }

        System.out.println(result);


    }


}


class Node {

    private boolean isChecked;
    private int data;
    private Node father;
    private ArrayList<Node> nodes;

    public Node getFather() {
        return father;
    }

    public void setFather(Node father) {
        this.father = father;
    }

    public boolean isChecked() {
        return isChecked;
    }

    public void setChecked(boolean checked) {
        isChecked = checked;
    }

    public Node(int data) {
        this.setChecked(false);
        this.data = data;
        this.father = null;
        nodes = new ArrayList<>();
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ArrayList<Node> getNodes() {
        return nodes;
    }

    public void setNodes(ArrayList<Node> nodes) {
        this.nodes = nodes;
    }
}