BaekJoon 1967번: 트리의 지름

트리의 지름을 구하는 알고리즘은 앞서 푼 BaekJoon 1167번: 트리의 지름 문제와 같다.

pearlcrum.tistory.com/4?category=989437

BaekJoon 1167번: 트리의 지름

풀이법

1) 아무 노드 a (이 코드의 경우 1)를 이용해서 a에서 가장 먼 점인 x를 구한다.

2) x에서 가장 먼 노드인 y를 구하고 x-y 간의 거리를 구한다. (지름 구하기)

3) BFS를 이용하여 vistied 배열과 dist 배열을 사용하여 문제를 해결한다. 이 때 초기화를 잊지 말자

 

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

#define INF 10001
using namespace std;

int n;
vector<pair<int, int>> vec[INF];
int maxVal,maxIndex;
bool visited[INF];
int dist[INF];

int bfs(int num)
{
	for (int i = 1; i <= n; i++)
	{
		visited[i] = false;
		dist[i] = 0;
	}
	
	visited[num] = true;
	queue<int> q;
	q.push(num);
	maxVal = 0;
	maxIndex = 0;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (int i = 0; i < vec[now].size(); i++)
		{
			int next = vec[now][i].first;
			int w = dist[now]+vec[now][i].second;
			if (!visited[next])
			{
				dist[next] = w;
				if (w > maxVal)
				{
					maxVal = w;
					maxIndex = next;
				}
				visited[next] = true;
				q.push(next);
			}
		}
	}
	return maxIndex;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int parent, child, weight;
		cin >> parent >> child >> weight;
		vec[parent].push_back({ child,weight });
		vec[child].push_back({ parent,weight });
	}
	int x=bfs(1);
	bfs(x);
	cout << maxVal;
}

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest