1967번 - 트리의 지름, 직관적 풀이법

https://www.acmicpc.net/problem/1967

문제의 초점을 트리보다는 직관적인 부분을 고려해서 문제를 설명해보려고 한다.
증명보다는 이미 알고 있는 지식, 직관으로부터 문제를 해결해보자.

문제에서는 정점끼리의 가장 긴 길이를 물어보고 있다.

위 그림에서 가장 긴 선은 무엇인가? A와 C를 잇는 선이다.
왜? AC 선분이 제일 길까? 그냥 제일 길어서다.

긴 선분보다 정점의 관점에서 다시 바라보자.
가장 멀리 있는 정점 2개를 고르면 가장 긴 길이를 갖는 선분을 가지게 된다.

그렇다면 가장 멀리있는 정점 2개를 어떻게 고를까?

A에서 C가 가장 멀다.
B에서 C가 가장 멀다.
D에서 C가 가장 멀다.
C에서 D가 가장 멀다.

가장 먼 정점은 어느 정점을 골라도 2개로 좁혀진다.이에 대한 설명을 귀류법으로 설명하던데... 난 못 하니 넘어간다.
=> 다른 블로그를 참고하시길 추천한다.

여튼 간에 이렇게 그은 선분을 좀 더 친분한다. 이를 다른 방식으로 그려보면 다르게 다가온다.
A부터 D까지의 길이는 다음 그림과 같이 생겼다.

사실 이를 쭉 펴보면..

이런걸 형이상학적..? 하여튼.. 이 그림을 통해 트리도 동일하다는 사실을 알 수 있다.

결국에 어떤 정점을 골라도, 결국 가장 먼 정점 2개 중 하나를 구할 수 있다.
보통 임의의 정점이라고 설명하고 말하지만, Root 노드를 사용한다.
그래서 Root 노드로부터 가장 먼 정점은 9번이고, 이 9번 정점으로부터 가장 먼 정점은 나머지 가장 먼 정점이 된다.
즉, 9번 노드로부터 가장 먼 정점까지의 거리만 구해주면 이 문제는 해결된다.

 처음 문제를 읽었을 때에는 어떤 정점을 골라야 가장 긴 정점이 되는지 이해가 안 가서 모든 정점의 길이를 구해서 가장 긴 값을 사용하고자 했다. 하지만 문제에서는 트리라는 구조의 특징(각 정점의 길이는 유일, 사실 이게 왜 특징인지 모르겠다.)을 이용하여 해당 문제를 해결하는 Key가 된다.

결국 나는 기초적인 직관에 의해 문제를 이해하였다. 다른 똑똑한 분들이 수학적 증명을 이용해서 해당 문제를 설명해주었으면 한다.

그리고 해당 문제는 DFS/BFS의 응용 문제로 보면 되는데, 그저 알고리즘을 적용하여 다 풀었다고 끝나기엔 아까운 문제이다. 보다 트리의 특징, 나는 직관에 이해 등에 관심을 두고 생각해보았다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<pair<int, int>>> nodes;
vector<bool> visited;

int furthestNode = 0;
int answer = -1;

void dfs(int target, int weight) {
    if (visited[target]) return;

    visited[target] = true;
    if (answer < weight) {
        answer = weight;
        furthestNode = target;
    }

    const auto& targetNode = nodes[target];
    for (int i = 0; i < targetNode.size(); i++) {
        dfs(targetNode[i].first, weight + targetNode[i].second);
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    nodes.resize(n + 1);
    
    for(int i = 0; i < n - 1; i++) {
        int a, b, c; cin >> a >> b >> c;
        nodes[a].push_back({ b, c });
        nodes[b].push_back({ a, c });
    }

    visited.assign(n + 1, false);
    dfs(1, 0);
    
    visited.assign(n + 1, false);
    dfs(furthestNode, 0);
    
    cout << answer;
}