[백준/C++]#1967 - 트리의 지름

풀이

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

using namespace std;

struct Edge {
	int to;
	int cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};
vector <Edge> A[10001];
bool check[10001];
int dist[10001];

void bfs(int start) {
	memset(dist, 0, sizeof(dist));
	memset(check, false, sizeof(check));
	check[start] = true;
	queue <int> q;
	q.push(start);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i=0; i<A[x].size(); i++) {
			Edge &e = A[x][i];
			if (check[e.to]==false) {
				q.push(e.to);
				check[e.to]=true;
				dist[e.to]= dist[x] + e.cost;
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	for (int i=0; i<n-1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		A[a].push_back(Edge(b, c));
		A[b].push_back(Edge(a, c));
	}
	bfs(1);
	int start = 1;
	for (int i=2; i<=n; i++) {
		if (dist[start] < dist[i]) {
			start = i;
		}
	}
	bfs(start);
	int ans = dist[1];
	for (int i=2; i<=n; i++) {
		if (ans < dist[i]) {
			ans = dist[i];
		}
	}
	cout << ans;
	return 0;
}

개념

https://etyoungsu.tistory.com/76

[백준/C++]#1167 - 트리의 지름

이전 문제와 동일한 개념을 가진다.

---

풀이

 

입력 받는 부분에서 조금 차이가 있다. 더욱 간단하다.

트리는 두 노드 사이에 하나의 경로만 존재한다.

이는 노드가 n개이면, 간선은 n-1개 라는 것을 의미한다.

 

n을 입력받고, n-1번 간선을 입력받는다.

 

A[a].push_back(Edge(b, c));
A[b].push_back(Edge(a, c));

 

각각 노드 a에 다음 노드b와 가중치 c 저장을 한다.

그리고 노드 b에 다음 노드a와 가중치 c를 저장한다.

무방향그래프이기 때문이다.