백준 1167 트리의 지름 C++

출처 : https://www.acmicpc.net/problem/1167

 

트리의 지름 구하는 법:

1. 임의의 정점x를 정한다.

2. x에서 가장 멀리있는 정점 y를 구한다.

3. y에서 가장 멀리 있는 정점까지의 거리가 트리의 지름이다.

 

출처 : https://blog.myungwoo.kr/112

트리의 지름 구하기

 

위에서 나온 트리의 지름을 구하는 방법만 알고 있으면 dfs를 이용해서 쉽게 구현할 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

const int INF = 987654321;

int v;

map<int, vector<pair<int, int>>> mp;
vector<bool> visited;

int ans = 0;
int start2 = 0;

void Dfs(int start, int sum) {
	if (visited[start]) return;
	visited[start] = true;
	if (sum > ans) {
		ans = sum;
		start2 = start;
	}
	for (auto next : mp[start]) {
		Dfs(next.first, sum + next.second);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> v;
	visited = vector<bool>(v + 1, false);
	for (int i = 0; i < v; i++) {
		int start;
		cin >> start;
		while (true) {
			int end;
			cin >> end;
			if (end == -1) break;
			int dist;
			cin >> dist;
			mp[start].push_back({ end,dist });
		}
	}
	Dfs(1, 0);
	visited.clear();
	visited = vector<bool>(v + 1, false);
	ans = 0;
	Dfs(start2, 0);
	cout << ans;
};