본문 바로가기

Problem Solving/Baekjoon OJ

[BOJ 1167] 트리의 지름

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

 

널리(?) 알려진 것과 달리 dfs 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다.

 

풀이

 

임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이는 dfs를 돌면서 잘 관리해줄 수 있다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> ad[100001];
int mx;
int dfs(int u,int p) {
	int mx1=0,mx2=0;
	for(auto &[v,d] : ad[u]) if(v^p){
		int dep=d+dfs(v,u);
		if(dep>=mx1) mx2=mx1, mx1=dep;
		else if(dep>mx2) mx2=dep;
	}
	mx=max(mx,mx1+mx2);
	return mx1;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	for(int i=1;i<=n;i++){
		int u,v,d; cin >> u;
		while(1){
			cin >> v; if(!~v) break;
			cin >> d;
			ad[u].push_back({v,d});
		}
	}
	dfs(1,0); cout << mx;
}

'Problem Solving > Baekjoon OJ' 카테고리의 다른 글

와 2000문제!  (2) 2022.03.24
First Solve 3개  (0) 2021.11.16
[BOJ 1167] 트리의 지름  (0) 2021.10.24
[BOJ 12784] 인하니카 공화국  (0) 2021.10.19
[BOJ 16998] It’s a Mod, Mod, Mod, Mod World  (0) 2021.10.17
Ruby V  (3) 2021.08.31