[ boj : 1595 ] 북쪽나라의 도로

https://www.acmicpc.net/problem/1595

1595번: 북쪽나라의 도로

해설 : 이 문제는 엄청나게 유명한 웰논문제입니다. 그냥 트리의 지름을 찾는 문제이죠. 

dfs 2번을 돌리면 답을 찾을 수 있다는 것이 증명이 되어있지만, 이번에는 tree dp 로 풀어보았습니다.

 

과정은 이렇습니다.

 

dfs를 돌리면서 부모-자식 간의 가중치를 return 시켜줍니다. 이때 루트노드까지 도달했을때는 넘겨받은 값들을 vector에 담아줍니다. 그러면 루트로부터 각 리프노드까지 거리가 얼마나 되는지 알 수 있겠죠?

 

그 vector를 sort 하여 2개를 뽑아줍니다. 이때 주의할 점은 정점이 단 2개만 존재할때는 0번 index만 뽑아오면 되고, 입력자체가 주어지지 않는 경우도 있더라구요. 이럴때 0을 출력해 주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int visit[10010],child[10010];
vector<pair<int,int>> v[10010];
vector<int> li;

int dfs(int x);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int x, y, w;
	while (true) {
		cin >> x;
		if (cin.eof())break;
		cin >> y >> w;

		v[x].push_back({ y,w });
		v[y].push_back({ x,w });
	}
	
	dfs(1);
	sort(li.begin(), li.end(), [](const int& a, const int& b) {
		return a > b;
	});
	if (li.size() >= 2)
		cout << li[0] + li[1];
	else if (li.size() == 1)
		cout << li[0];
	else
		cout << 0;
	return 0;
}
int dfs(int x)
{
	visit[x] = 1;
	for (int i = 0; i < v[x].size(); i++) {
		if (!visit[v[x][i].first]) {
			int ret = dfs(v[x][i].first) + v[x][i].second;
			if (x == 1)
				li.push_back(ret);
			child[x] = max(child[x], ret);
		}
	}
	return child[x];
}