백준 1967번: 트리의 지름

[문제 링크]

1967번: 트리의 지름

---

간단한 문제였다. 모든 정점을 시작점으로 bfs나 dfs를 수행하여 그중 최댓값을 찾으면 정답을 받을 수 있다.

하지만 이 문제를 더 빠르게 풀 수 있는 방법이 존재한다고 한다. 

 

뿌리노드인 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점을 시작점으로 하여 가장 멀리 떨어진 정점까지의 거리가 곧 트리의 지름이 된다. 따라서 탐색을 2번 수행하므로 O(n) 시간에 문제를 해결할 수 있다.

 

자세한 증명은 구사과님의 블로그에 설명되어 있다.

https://koosaga.com/14

트리의 지름 (Diameter of tree)

---

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

int N;
vector<vector<pair<int, int>>> adj(10001);
bool visited[10001];

pair<int, int> bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	pair<int, int> ret = { 0,0 };
	while (!q.empty()) {
		int here = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (ret.second < cost)
			ret = { here, cost };

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

			if (!visited[there]) {
				visited[there] = true;
				q.push({ there, nextCost });
			}
		}
	}

	return ret;
}


int main(void) {
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	// find maximum node
	int maxNode = bfs(1).first;

	memset(visited, false, sizeof(visited));

	// get diameter
	int diameter = bfs(maxNode).second;

	cout << diameter << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day