13. 트리의 높이. 트리의 높이

문제

---

트리의 높이는 루트로부터 가장 멀리 떨어진 노드와의 거리로 정의된다. 예를 들어, 아래의 트리에서 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

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;


// stack에 들어가면 방문한거로 판단
// 해당 위치를 true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]) {
	int max = 0;
	stack<int> s;
	s.push(start);
	check[start] = true;
	//printf("%d ", start);

	while (!s.empty()) {

		int current_node = s.top();
		s.pop();
		for (int i = 0; i < graph[current_node].size(); i++) {

			int next_node = graph[current_node][i];

			if (check[next_node] == false) {
				//printf("%d ", next_node);
				check[next_node] = true;
				// pop()을 했었기 때문에 현재 current_node도 넣어줘야한다.
				s.push(current_node);
				s.push(next_node);
				
				if (max < s.size()) {
					max = s.size();
				}
				break;
			}
		}
	}

	if (max == -1) max = 0;
	printf("%d", max-1);
}

int main() {
	int n, root;
	scanf("%d %d", &n, &root);

	vector<int> graph[1000];
	bool check[1000];
	fill(check, check + n + 1, false);

	for (int i = 1; i < n; i++) {
		int parent, node;
		scanf("%d %d", &parent, &node);
		graph[parent].push_back(node);
		graph[node].push_back(parent);

	}
	

	// Sorting은 한 이유
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs
	if (n == 1) printf("%d", 0); 
	else {
		dfs(root, graph, check);
		printf("\n");
	}
	
	return 0;
}