백준 1167번: 트리의 지름

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

트리의 지름은 가중치가 들어간 그래프(트리)를 탐색해서 가장 큰 값을 구하는 거다.

그러기 위해선 가장 위에 있는 루트 값을 알아내야 한다.

그리고 그 루트에서 가장 큰 값을 구하면 그게 가장 큰 값이 된다.

즉 루트를 알아내기위한 탐색 1번과 루트를 기준으로 가장 큰 값을 구하는 탐색 2번이면 구해진다.

#include<iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;
#pragma warning(disable : 4996)
vector<pair<int,int>> d[100020];    //pair을 이용한 배열 저장
bool check[100020];               //방문 체크
int dept[100020];                 //트리의 길이 값 저장
void dfs(int a,int len) {             //탐색
	check[a] = true;
	dept[a] = len;                //길이 저장
	for (int i = 0; i < d[a].size(); i++) {
		int next = d[a][i].first;
		if (check[next] == false) {
			len = dept[a]+ d[a][i].second;          
			dfs(next, len);
		}
	}
}
int main() {
	int n;
	int root = 1;
	cin >> n;
	for(int i=0;i<n;i++){
		int a, b, c;
		cin >> a;
		while (1) {
			cin >> b;
			if (b == -1)
				break;
			cin >> c;
			d[a].push_back(make_pair(b, c));
		}
	}
	dfs(1, 0);          //일단 1로 탐색
	int max = dept[1];   
	for (int i = 2; i <= n; i++) {
		if (max < dept[i]) {
			max = dept[i];
			root = i;            //가장 멀리 있는 값을 루트로 정함
		}
	}
	memset(check, false, sizeof(check));          //체크 배열 false으로 초기화
	dfs(root, 0);              //루트로 탐색
	max = dept[root];
	for (int i = 1; i <= n; i++) {          
		if (max < dept[i]) {
			max = dept[i];
		}
	} 
	cout << max;
	return 0;
}