백준14657 준오는 최종인재야!!

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14657

문제 출처

  • 제1회 천하제일 코딩대회 본선 H번

사용 알고리즘

  • 트리의 지름

시간복잡도

  • O(n)

풀이

트리의 지름 관련 문제입니다.
나올 수 있는 모든 트리의 지름 중, 간선의 합이 가장 작은 지름을 구하는 문제입니다.

트리의 지름을 구하는 방법은 다음과 같습니다.

  1. 아무 노드에서 가장 멀리 떨어져 있는 노드 t를 잡습니다.(DFS 사용)
  2. t에서 가장 멀리 떨어진 노드 u를 잡습니다.(DFS 사용)
  3. t에서 u까지가 트리의 지름입니다.

DFS 2번 사용으로 O(n)으로 구할 수 있습니다.
증명은 koosaga님이 쓰신 글에 나와있습니다. http://koosaga.com/14

이 문제는 해결 순서가 아닌, 코드 설명으로 풀이를 할 것입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;
typedef pair<pair<int, int>, int> pi; //< <깊이, -1*거리>, 현재 노드>

vector<p> gph[50010]; //인접리스트 <노드, 거리>
int n, t;

pi dfs(int now, int par, int dph){ //(현재, 이전 노드, 깊이)
	pi ret = make_pair(make_pair(dph, 0), now);
	for(int i=0; i<gph[now].size(); i++){
		int next = gph[now][i].first; //다음 노드
		int dist = gph[now][i].second; //next까지의 거리
		if(next == par) continue; //이전 노드와 다음 노드가 같으면 skip
		pi tmp = dfs(next, now, dph+1);
		tmp.first.second -= dist;
		ret = max(ret, tmp);
	}
	return ret;
}

int main(){
	cin >> n >> t;
	for(int i=0; i<n-1; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		gph[a].push_back({b, c});
		gph[b].push_back({a, c});
	}

	int root = dfs(1, 0, 0).second; //루트에서 가장 멀리 떨어진 노드
	int ans = -dfs(root, 0, 0).first.second; //정답
	printf("%d", (ans+t-1)/t);

}