[백준/BOJ] 백준 1167번 : 트리의 지름

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

1167번: 트리의 지름

 

임의의 지점(아래 코드에서는 1번 정점)에서 가장 먼 지점인 a를 찾고, a에서 가장 먼 지점인 b를 찾아서 a와 b사이의 거리를 구하는 방법으로 트리의 지름을 구해서 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<pair<int, int>> adj[100005];
int visited[100005];
int dist[100005];

void pre() {
	for (int i = 0; i < 100005; i++) {
		visited[i] = 0;
		dist[i] = 0;
	}
}

void dfs(int here, int add_dist) {
	visited[here] = 1;
	dist[here] = add_dist;

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i].second;
		int cost = adj[here][i].first;

		if (visited[there] == 0) {
			dfs(there, add_dist + cost);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int u;
		cin >> u;

		while (1) {
			int v, cost;

			cin >> v;

			if (v == -1) {
				break;
			}

			cin >> cost;

			adj[u].push_back(make_pair(cost, v));
			adj[v].push_back(make_pair(cost, u));
		}
	}

	//임의의 지점(1번 정점)에서 가장 먼 지점인 a를 찾고, a에서 가장 먼 지점인 b를 찾아서 a와 b사이의 거리를 구한다
	int a = -1;
	int b = -1;
	int a_cost = -1;
	int b_cost = -1;
	int result;

	pre();
	dfs(1, 0);

	for (int i = 1; i <= n; i++) {
		if (dist[i] > a_cost) {
			a = i;
			a_cost = dist[i];
		}
	}

	pre();
	dfs(a, 0);

	for (int i = 1; i <= n; i++) {
		if (dist[i] > b_cost) {
			b = i;
			b_cost = dist[i];
		}
	}

	result = dist[b]; //a~b사이의 거리

	cout << result;

	return 0;
}