(c++)백준 1967번: 트리의 지름

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

1967번: 트리의 지름

[풀이]

각 노드를 시작점으로 하여 bfs를 돌려보고 각 노드에서 가장 먼 노드까지의 길이중 가장 긴 것을 출력한다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>//max
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, cnt;
};

struct Weight {
	int x, weight;//이어진 노드, 간선 가중치
};

int n;
vector<Weight>W[10001];
bool check[10001];
int Max = -1;

void bfs(int start) {
	queue<Pos>q;
	q.push({ start,0 });
	check[start] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int cnt = q.front().cnt;
		q.pop();
		for (int i = 0; i < W[x].size(); i++) {
			int nx = W[x][i].x;
			int weight = W[x][i].weight;
			if (!check[nx]) {
				check[nx] = true;
				q.push({ nx,cnt + weight });
				Max = max(Max, cnt + weight);
			}
		}
	}
}

void solution() {
	cin >> n;
	int a, b, w;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> w;
		W[a].push_back({ b,w });
		W[b].push_back({ a,w });
	}
	for (int i = 1; i <= n; i++) {
		memset(check, false, sizeof(check));
		bfs(i);
	}
	cout << Max << endl;
}
int main() {
	solution();
	return 0;
}