문제
트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.
이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.
입출력
•
입력
1 - 노드의 개수(N)
2 ~ N+1 - 부모노드, 자식노드, 가중치
•
출력
트리의 지름
//입력
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10
//출력
45
C++
복사
풀이
트리의 지름을 구하는 법
1.
한 점에서 가장 먼 점을 선택한다. (u)
2.
그 점에서 가장 먼 점을 선택한다. (v)
3.
두 점 사이의 거리가 트리의 지름이다 d(u,v)
귀류법을 통한 증명 ->
정답을 구하는법
1.
dfs를 통해 가장 먼 거리의 정점을 찾기
2.
다익스트라를 통해 가장 먼 거리의 정점을 찾기
•
다익스트라 함수 (최단거리 구하기)
- start : 시작지점
void dijk(int start) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({ 0, start });
dist[start] = 0;
while (!pq.empty()) {
auto [cost, idx] = pq.top(); pq.pop();
if (dist[idx] < cost) continue;
for (auto [nidx, ncost] : graph[idx]) {
if (dist[nidx] > cost + ncost) {
dist[nidx] = cost + ncost;
pq.push({ ncost + cost, nidx });
}
}
}
}
C++
복사
•
find_max 함수 (가장 먼 곳 찾기)
- start : 시작지점
- max_result : 먼곳까지의 거리
- max_idx : 먼 곳의 번호
pii find_max(int start) {
int max_result = 0, max_idx;
for (int i = 1; i <= N; i++) {
if (max_result < dist[i]) {
max_idx = i;
max_result = dist[i];
}
}
return { max_result, max_idx };
}
C++
복사
•
Main 함수 동작
int main() {
fastio;
int a,b,c;
cin >> N;
for (int i = 1; i <= N - 1; i++) {
cin >> a >> b >> c;
graph[a].push_back({ b,c });
graph[b].push_back({ a,c });
}
init();
dijk(1);
int mid_result = find_max(1).snd;
init();
dijk(mid_result);
int final_result = find_max(mid_result).fst;
cout << final_result;
return 0;
}
C++
복사
