백준 1967번 트리의 지름

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

1967번: 트리의 지름

트리디피와 그리디로 각각 문제를 풀었다.

 

 

트리DP 풀이

트리의 지름은 지름이 지나는 가장 깊이가 낮은 노드를 루트로 하는 서브트리에 포함된다.

이때 해당 노드를 한 끝점으로 하는 경우와 노드를 지나면서 자식 노드들 중 둘을 지나는 경우로 나눌 수 있다.

 

dp[a]를 a번 노드를 루트로 하면서 자식 노드들 중 하나만을 지나는 경로의 길이로 하였고 모든 노드에 대해 최대 두개의 자식 노드의 dp의 합 + 각 자식 노드와의 거리를 구하면 답이 된다.

 

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

vector<vector<pair<int, int>>> tree;
vector<int> dp;
int ans = 0;

void dfs(int a, int b){
	for (const pair<int, int>& i : tree[a]){
		if (i.first == b) continue;
		dfs(i.first, a);
		ans = max(ans, dp[a] + dp[i.first] + i.second);
		dp[a] = max(dp[a], dp[i.first] + i.second);
	}
	ans = max(ans, dp[a]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, a, b, dis;
	cin >> n;
	tree.resize(n);
	dp.resize(n);

	for (int i = 1; i < n; i++){
		cin >> a >> b >> dis;
		tree[--a].push_back({ --b, dis });
		tree[b].push_back({ a, dis });
	}

	dfs(0, -1);

	cout << ans << '\n';

	return 0;
}

 

 

그리디 풀이

트리의 한 노드를 잡고 이를 a라 하자. 그리고 이 노드에서 가장 먼 노드를 b, 지름의 양 끝을 각각 x, y라 둔다.

a, b의 경로와 지름이 하나 이상의 노드를 공유할 때, b가 x또는 y보다 a로부터 멀다는 것은 a,b의 경로와 지름이 만나는 노드들중 하나로 부터도 x또는 y보다 b가 더 멀다는 말이 되고 x 또는 y로부터도 반대쪽 지름의 끝 보다 b가 더 머니 모순이 생겨 b는 지름의 한 끝이 된다.

또 다른 경우에서 a, b의 경로와 지름이 만나지 않으며 b는 x 또는 y가 아니라고 해 보자.

이때 두 경로위의 점들중 하나씩을 서로 이어주는 또다른 경로가 하나 이상 생기는데 이 경로가 a, b의 경로와 만나는 노드를 c, 지름과 만나는 노드를 d라고 하자.

이때 x -> y는 x -> d -> y이고 x -> d -> c -> b보다 깁니다. 여기서 d -> y도 d -> c -> b보다 길다.

a에서 봤을때도 a -> c -> b가 a -> c -> d -> y보다 깁니다. 여기서 d -> y를 d -> c -> b로 바꾸어줘도 길이가 더 짧아져 둘의 대소관계가 성립해야 하는데 반대로 a -> c -> d -> c -> b가 a -> c -> b보다 기니 마찬가지로 모순이라 b는 지름의 한쪽 끝이라는것을 알 수 있다.

 

이제 한 점을 a로 잡고 b를 찾은 후 다시 그 점에서 가장 먼 노드와의 거리를 구하면 지름이 된다.

 

 

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

vector<vector<pair<int, int>>> tree;
int ans = 0;
/*
d1 : 0번 노드와 가장 먼 노드 사이의 거리
d : 0번 노드와 가장 먼 노드의 번호
d2 : 지름
*/
int d1, d2, d;

/*
d1과 d를 찾는 함수
b번 노드를 부모로 가진 a번 노드는 루트노드와의 거리가 c이다.
*/
void dfs1(int a, int b, int c){
	if (c > d1){
		d1 = c;
		d = a;
	}
	for (const pair<int, int>& i : tree[a]){
		if (i.first == b) continue;
		dfs1(i.first, a, c + i.second);
	}
}

/*
d2를 찾는 함수
b번 노드를 부모로 가진 a번 노드는 d번 노드와의 거리가 c이다.
*/
void dfs2(int a, int b, int c){
	d2 = max(d2, c);
	for (const pair<int, int>& i : tree[a]){
		if (i.first == b) continue;
		dfs2(i.first, a, c + i.second);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, a, b, dis;
	cin >> n;
	tree.resize(n);

	for (int i = 1; i < n; i++){
		cin >> a >> b >> dis;
		tree[--a].push_back({ --b, dis });
		tree[b].push_back({ a, dis });
	}

	dfs1(0, -1, 0);
	dfs2(d, -1, 0);

	cout << d2;

	return 0;
}