[백준 1167] 트리의 지름 (C++)

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

1167번: 트리의 지름

1. 주의할 점

- 모든 Node에 대해 돌릴 경우 N^2 -> 시간초과 발생

- 시작 Node를 기준으로 Leaf 까지의 거리를 이용

 

2. 구현

- 트리의 지름이 되는 경우는 크게 2가지다

 첫 번째로 트리가 1자 형태로 되어 있어서 시작점부터 Leaf Node까지의 거리다

 두 번째로 시작점에서 여러 Node로 갈 수 있을 때(2개 이상의 Node), 시작점부터 각 Leaf까지의 Node의 거리를 구한다. 만약 LeafNode의 조상(시작 Node의 자손이라고 가정)이 다를 경우 이들 합의 최대를 구한다.

2가지 가정을 모두 만족시키면서 구할 수 있는 방법은 다음과 같다.

 1) 시작점 -> 최대거리 가지는 Node

 2) 최대거리 가지는 Node -> 각 Node까지의 거리 중 최대값

 

- 시작 Node를 1로 두고 다익스트라 알고리즘을 통해 최대거리를 가지는 Node를 구한다

- 위에서 구한 Node를 바탕으로 다익스트라 알고리즘을 통해 최대거리의 길이을 구한다.

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
vector<info> v[100001];
int dist[100001], result = 0, maxleaf = 0, maxi, node;
void dijkstra(int start) {
	for (int i = 1; i <= node; i++) 
		dist[i] = MAX;	
	queue<info> q;
	tmp.idx = start;
	tmp.val = 0;
	q.push(tmp);
	dist[start] = 0;
	maxi = 0;
	while(!q.empty()) {
		int cidx = q.front().idx;
		int cv = q.front().val;
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = v[cidx][i].val;
			if (dist[next] > cv + nv) {
				dist[next] = cv + nv;
				tmp.idx = next;
				tmp.val = cv + nv;
				q.push(tmp);
				if (cv + nv > maxi) {
					maxi = cv + nv;
					maxleaf = next;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, start, val;
	cin >> node;
	for (int i = 1; i <= node; i++) {
		cin >> n;
		while (1) {
			cin >> start;
			if (start == -1) break;
			cin >> val;
			tmp.idx = start;
			tmp.val = val;
			v[n].push_back(tmp);
			tmp.idx = n;
			v[start].push_back(tmp);
		}
	}
	dijkstra(1);
	dijkstra(maxleaf);
	cout << maxi;
	system("pause");
	return 0;
}