트리의 높이

트리의 높이

 

문제

---

트리의 높이는 루트로부터 가장 멀리 떨어진 노드와의 거리로 정의된다. 예를 들어, 아래의 트리에서 0번 노드가 루트라고 하면, 7번 노드까지의 거리가 가장 멀고, 그 거리는 3이다. 따라서 이 트리의 높이는 3이 된다.

트리가 주어질 때, 그 트리의 높이를 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 트리의 노드 개수 n, 그리고 루트노드의 번호 r이 주어진다. ( 1 ≤ r ≤ n ≤ 100 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 a번 노드와 b번 노드가 연결되어 있다는 뜻이다.  

출력

---

트리의 높이를 출력한다.

 

예제 입력

8 0
0 1
0 2
1 3
1 4
1 5
2 6
6 7

예제 출력

3

코드

//트리의 높이

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 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();

        Node find1 = box.get(b);
        find1.setHeight(0);

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

        for (int i = 0; i < box.size(); i++) {
            if (result < box.get(i).getHeight()) result = box.get(i).getHeight();
        }

        System.out.println(result);


    }


}


class Node {
    public int getHeight() {
        return height;
    }

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

    private boolean isChecked;
    private int data;
    private Node father;
    private int height;
    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;
        this.height = 0;
        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;
    }
}