골드3 : dfs 문제이다.
풀이
트리 = 사이클이 없는 무방향 그래프. 어떠한 두 노드를 선택해도 경로는 하나이다. 즉 무조건 연결되어 있다. 쉽게 생각하기 위해서 이미 두 지름인 점을 알고 있다고 가정하자. 그럼 그 두 점을 잡고 쭉 늘리면 가장 긴 거리가 될 것이다. 자 이제, 그 두 점을 기준으로 원을 만들면 그 안에 모든 노드가 존재하게 된다. 그 안의 노드중 아무거나 선택해보자. 그리고 그곳으로부터 지름의 점으로 선잇기를 해보자. 그럼 무조건 갈 수 있다. 이게 핵심이다. 모든 노드는 1개 이상의 간선을 가지고 있기 때문에, 지름을 표현하는 그 점으로 가능 방법이 존재한다. 그리고 그 방법은 길이의 최대를 만족하는 지점의 노드를 구하는 것이다. 즉, 어느점에서라도 거리가 가장 길어지는 지점을 찾을 수 있다면, 그것이 최대 길이의 한 점이다. 그 뒤는 쉽다. 최대 길이의 한 점에서 출발해서 최대 길이를 구하면 된다.
- 특정 노드로부터 시작하여 최대 길이를 가지는 노드를 구한다.
- 그 노드에서부터 최대 길이를 구한다.
만약, 각각의 노드에서 dfs를 통해 값을 구한다면, 정도의 시간 복잡도가 발생하고, V가 100,000이기 때문에 불가능하다. 위의 방법으로 진행할 경우, 만에 탐색이 가능하다.
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
vector<pair<int, int>> graph[100001];
bool visited[100001];
ll maxDist = 0;
int maxIndex = 0;
void dfs(int node, int cost){
if (maxDist < cost) {
maxDist = cost;
maxIndex = node;
}
visited[node] = true;
for (int i = 0; i < graph[node].size(); i++) {
int nextNode = graph[node][i].first;
int weight = graph[node][i].second;
if (visited[nextNode]) continue;
dfs(nextNode, cost+weight);
}
}
int main(){
int n;
cin >> n;
int a, b, c;
for (int i = 0; i < n; i++) {
cin >> a;
while (true) {
cin >> b;
if (b < 0) break;
cin >> c;
graph[a].push_back(make_pair(b, c));
}
}
dfs(1, 0); // 어느 점에서 출발해도 상관 없음. 1번 노드는 무조건 존재한다.
for (int i = 0; i <= n; i++) {
visited[i] = false;
}
maxDist = 0;
dfs(maxIndex, 0);
cout << maxDist << '\n';
return 0;
}