[BOJ] 1167 : 트리의 지름 - travelbeeee

문제 : https://www.acmicpc.net/problem/1167

---

[ 알고리즘 풀이 ]

가장 긴 트리의 지름을 정하는 두 노드는 리프 노드다. ( 리프 노드가 아니면, 더 갈 수 있으므로 최대 지름일 수가 없다. ) 따라서, 우리는 리프 노드 2개를 골라 탐색을 하며 거리를 계산해봐야 되는데 이때, 모든 리프 노드 쌍에 대해서 탐색을 진행하면  정점이 100,000 개라 최악의 경우 (100,000)^2 번에 가까운 탐색이 진행돼 시간초과 문제에 걸리게 된다. 따라서, 임의의 리프 노드에서 BFS 탐색을 진행해 거리가 최대가 되는 순간의 리프 노드를 하나 찾고( 가장 긴 트리의 지름 중 하나의 노드 ) 다시 찾은 노드에서 BFS 탐색을 진행하면 가장 긴 트리의 지름을 찾을 수 있다.

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

using namespace std;

int V, s, x, y;
vector<pair<int, int>> graph[100001];
bool visited[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> V;
	for (int i = 0; i < V; i++) {
		cin >> s;
		while (1) {
			cin >> x;
			if (x == -1)
				break;
			cin >> y;
			graph[s].push_back({ x,y });
			graph[x].push_back({ s,y });
		}
	}

	int start = 1;
	for (int i = 1; i <= V; i++) {
		if (graph[i].size() == 2){
			start = i;
			break;
		}
	}
	
	int ans = 0;
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = 1;

	int endNode = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		if (ans < cur.second) {
			endNode = cur.first;
			ans = cur.second;
		}

		for (int i = 0; i < graph[cur.first].size(); i++) {
			if (visited[graph[cur.first][i].first])
				continue;
			visited[graph[cur.first][i].first] = 1;
			q.push({ graph[cur.first][i].first, cur.second + graph[cur.first][i].second });
		}
	}

	memset(visited, 0, sizeof(visited));
	q.push({ endNode, 0 });
	visited[endNode] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		ans = max(ans, cur.second);

		for (int i = 0; i < graph[cur.first].size(); i++) {
			if (visited[graph[cur.first][i].first])
				continue;
			visited[graph[cur.first][i].first] = 1;
			q.push({ graph[cur.first][i].first, cur.second + graph[cur.first][i].second });
		}
	}

	cout << ans;
}

---