트리의 거리

트리에서의 거리 1

 

문제

---

트리가 주어지고, 두 노드 X, Y가 주어질 때, 이 두 노드 사이의 거리를 출력하는 프로그램을 작성하시오. 트리에서는 두 노드를 잇는 경로가 유일하기 때문에, 정답은 항상 유일하다는 것을 참고한다. 예를 들어, 다음과 같은 트리에서 노드 3, 노드 6 사이의 거리는 4이다.

 

입력

---

첫 번째 줄에 트리의 노드 개수 n, 두 노드 X, Y의 번호가 주어진다. ( 1 ≤ X, Y ≤ n ≤ 1000 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 노드 a가 노드 b의 부모노드라는 것을 의미한다. 루트는 노드 0이라고 가정한다.  

출력

---

두 노드 X, Y 사이의 거리를 출력한다.

 

예제 입력

11 3 6
0 1
0 2
1 3
1 4
1 5
2 6
2 10
6 7
6 8
6 9

예제 출력

4

코드

//트리에서의 거리

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;

        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));
            box.get(d).setHeight(box.get(c).getHeight() + 1);
        }

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

        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()) {
                    resultNode = fatherBox.get(i);
                    break fullFor;
                }
            }
        }

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

        System.out.println(find1.getHeight() + find2.getHeight() - (2 * resultNode.getHeight()));


    }


}


class Node {

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

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    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.height = 0;
        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;
    }
}