반응형
https://www.acmicpc.net/problem/1167
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말합니다. 트리의 지름을 구하는 기본 알고리즘은 다음과 같습니다.
- 임의의 한 노드 A를 선택합니다.
- 노드 A에서 가장 먼 노드 B를 찾습니다.
- 노드 B에서 가장 먼 노드 C를 찾습니다.
- 노드 B와 노드 C 사이의 경로의 길이가 트리의 지름입니다.
더 긴 지름이 존재한다면 모순임을 보이면 증명됩니다.
코드는 다음과 같이 작성해 보았습니다.
#include <bits/stdc++.h>
using namespace std;
int v;
vector<pair<int, int>> tree[100001];
bool visited[100001];
pair<int, int> r = {1, 0};
void getFar(int i, int p)
{
visited[i] = true;
if (r.second < p)
r = {i, p};
for (auto [ii, pp] : tree[i])
{
if (visited[ii])
continue;
getFar(ii, p + pp);
}
visited[i] = false;
}
int main()
{
cin >> v;
for (int i = 0; i < v; i++)
{
int a, b = 0, c;
cin >> a;
while (b != -1)
{
cin >> b;
if (b == -1)
break;
cin >> c;
tree[a].push_back({b, c});
}
}
getFar(1, 0);
r.second = 0;
getFar(r.first, 0);
cout << r.second;
}
DFS를 두 번 이용하는 코드로, 첫 번째 DFS에서는 임의의 노드 (1번 노드)에서 가장 먼 노드를 찾아 r에 넣고, 해당 노드에서 다시 DFS를 돌려서 가장 먼 노드를 찾습니다. 이 때의 경로의 길이가 트리의 지름입니다.
관련 문제
반응형
댓글