문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
풀이
트리의 지름은 임의의 한 정점에서 가장 먼 정점을 찾고, 그 정점에서 다시 가장 먼 정점을 찾으면 구할 수 있다. 트리에는 사이클이 없기 때문에 이 두 번의 DFS만으로 지름의 한 끝과 전체 길이를 정확히 얻을 수 있다.
코드에서는 먼저 1번 정점에서 DFS를 시작해 가장 멀리 있는 정점 maxNode를 찾는다. 그다음 방문 배열을 초기화하고 maxNode에서 다시 DFS를 돌려 가장 멀리 도달한 거리 ans를 구한다. 이 두 번째 DFS의 최대 거리가 곧 트리의 지름이다.
입력은 한 정점 기준의 인접 정보가 양방향처럼 반복해서 주어지는데, 코드에서는 인접 리스트에 모두 넣고 방문 배열로 중복 순회를 막는다. 가중치가 있는 트리지만 최단 경로가 유일하므로 DFS로 누적 거리만 잘 더해 가면 된다.
코드
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 100001;
int ans = 0, maxNode = 0;
vector<pair<int, int>> vec[MAXN];
bool visit[MAXN];
void dfs(int node, int weight) {
if (visit[node])
return;
visit[node] = true;
if (ans < weight) {
ans = weight;
maxNode = node;
}
for (int i = 0; i < vec[node].size(); i++)
dfs(vec[node][i].first, weight + vec[node][i].second);
}
void solve() {
int V;
cin >> V;
for (int i = 0; i < V; i++) {
int node = 0, num = 0, weight = 0;
cin >> node;
while (true) {
cin >> num;
if (num == -1)
break;
cin >> weight;
vec[node].push_back({num, weight});
vec[num].push_back({node, weight});
}
}
dfs(1, 0);
ans = 0;
memset(visit, false, sizeof(visit));
dfs(maxNode, 0);
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
트리 지름의 정석은 역시 두 번의 DFS다. 한 번은 지름의 끝점을 찾고, 한 번은 그 끝에서 실제 길이를 재는 과정이라고 보면 된다.
