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

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

1967번: 트리의 지름

start에서 최장 거리(가장 큰 가중치)의 노드까지의 거리를 구하는 함수를 만들었다. 그리고 부모 노드들을 제외(leaf노드에서 leaf노드로 가는것만 지름이 될 수 있으므로)한 노드들을 start로 하여 최장 거리(가장 큰 가중치)의 노드까지의 거리를 구해 그중 가장 긴 거리를 찾았다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

int n;
vector<pair<int, int>> adj[10001];
int discovered[10001];
vector<int> parent_check(10001, 0);

//start에서 최장 거리(가장 큰 가중치)의 노드까지의 거리를 구한다
int Solve(int start)
{
	int ret = 0;

	//discovered에 해당 거리까지 가는데 거리(가중치의 값)을 저장한다
	discovered[start] = 0;

	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		ret = max(ret, discovered[here]);

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

			if (discovered[there] == -1)
			{
				//discovered에 해당 거리까지 가는데 거리(가중치의 값)을 저장한다
				discovered[there] = discovered[here] + adj[here][i].first;

				q.push(there);
			}
		}
	}

	return ret;
}

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

	int u, v, cost;
	int result = -1;

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		cin >> u >> v >> cost;
		adj[u].push_back(make_pair(cost, v));
		adj[v].push_back(make_pair(cost, u));
		parent_check[u] = 1; //부모 노드인것은 따로 체크한다
	}

	for (int i = 1; i <= n; i++)
	{
		//leaf노드에서 leaf노드로 가는것만 지름이 될수 있으므로 부모 노드인것은 넘어간다
		if (parent_check[i] == 1)
			continue;

		memset(discovered, -1, sizeof(discovered));
		result = max(result, Solve(i));
	}

	cout << result;

	return 0;
}