[실전 문제] 트리의 높이

1. 문제

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

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

---

입력

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

출력

트리의 높이를 출력한다.

예제 입력

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

예제 출력

3

 

 

 

2. 풀이

이 문제의 해결법은 DFS이다. 단, 방문하면서 그 때의 높이를 저장하여 해결해야한다. 이 문제의 해결법은 간단하다.

 

코드상에서 visitedHeight는 방문 여부와 높이를 처리하는 변수로, '-1' 일 경우 방문을 안했음을 뜻하고, 그 이외의 값들은 각 노드에서의 높이 정보를 뜻한다.

 

이 visitedHeight를 이용하여 가장 큰 값이 트리에서의 최대 높이임을 뜻한다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Graph {
    private ArrayList<ArrayList<Integer>> graph;

    public Graph(int nodeSize) {
        graph = new ArrayList<>();

        for(int i = 0; i < nodeSize + 1; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void put(int n, int m) {
        graph.get(n).add(m);
        graph.get(m).add(n);
    }

    public ArrayList<Integer> getNode(int n) {
        return graph.get(n);
    }
}

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int node;
    private static int rootNum;

    private static Graph graph;
    private static int[] visitedHeight;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        rootNum = Integer.parseInt(st.nextToken());

        graph = new Graph(node);
        visitedHeight = new int[node];
        Arrays.fill(visitedHeight, -1);
        
        for(int i = 0; i < node-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.put(a, b);
        }

        dfs(rootNum, 0);

        int max = -987987987;
        for(int i = 0; i < node; i++) {
            if(max < visitedHeight[i]) max = visitedHeight[i];
        }

        bw.write(max + " ");
        br.close();
        bw.flush();
        bw.close();
    }

    private static void dfs(int v, int height) {
        visitedHeight[v] = height;
        for(int i = 0; i < graph.getNode(v).size(); i++) {
            int w = graph.getNode(v).get(i);
            if(visitedHeight[w] == -1) {
                dfs(w, height+1);
            }
        }
    }

}