[백준/C++/Gold(2,4)] 1167, 1967 - 트리의 지름

 

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

1167번: 트리의 지름

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

1967번: 트리의 지름

 각각 난이도 G2와 G4에 해당하는 실질적으로는 똑같은 문제들이다. 입력방법만이 조금 다른데 문제가 이렇게 중복해서 있다니... 나같이 Solved.ac티어 환장한 사람들에게는 제격의 문제이다.

 

 우선 그래프이론에서 트리란, 고리가 없는, 순환 참조가 되지 않으면서 모든 정점이 연결되어있는 그래프를 의미한다.

고리가 없으므로 트리가 맞는 그래프이다.

고리가 있으므로 트리가 아닌 그래프이다.

 이러한 트리의 그래프 중에서 "제일 거리가 먼 두 점 사이의 거리"가 트리의 지름이다. 자세한 설명은 1967번의 그림을 보면서 이해하는 것이 직관적으로 좀 도움이 된다. 처음에 1167번을 읽어서 그런가 문제에 접근하기 어렵지 않다고 생각했다. 그냥 DFS로 제일 깊은 깊이를 찾으면 되는 게 아닐까?라고 생각해서 임의의 "말단" 노드를 선택해서 제일 깊은 깊이를 반환하는 코드를 짰고, 당연히 예제의 의도와 다르게 나올 때가 있었다. 예제의 그래프는 대강 다음과 같다.

와 이미지 재활용

이 트리의 지름은 11이다. 1 - 3 - 4 - 5의 노드를 잇는 구간이 제일 거리가 멀기 때문이다. 나는 말단 노드 1, 2, 5 중에서 하나를 골라서 지름을 계산하려 들었고, 그래서 1, 5를 골랐을 때는 제대로 값이 나왔지만 2를 골랐을 때는 10이라는 이상한 값이 나왔다. 2는 트리의 지름에 포함되지 않았기 때문이다. 거기까지는 좋았는데 그럼 어떻게 하지? 트리의 지름에 포함되는 말단 노드를 고를 방법이 있는 건가? 아님 설마 모든 말단 노드를 전부 검사해야 하나? 다행히도 그럴 필요가 없다! 나는 머리를 쥐어 싸맨 끝에 포기하고 대강 솔루션을 보기로 했는데, 솔루션은 다음과 같았다.

 

1. dfs를 이용해서 임의의 정점에서 제일 먼 정점 a를 찾는다.

2. 또 dfs를 써서 a에서 제일 먼 정점 b를 찾는다.

3. a-b사이의 거리가 트리의 지름이다.

 

근데 거기에 있는 증명은 따로 보지는 않았다. 왜 그렇게 되는지 골몰히 생각한 결과, 이런 기하학적으로 이걸 증명할 수 있게 되었다.

트리의 지름위에 모든 노드를 밀착시킨다. 이때 경로는 신경쓰지 않는다.

트리의 지름이 트리로 만들 수 있는 제일 큰 선분의 길이이므로, 나머지 정점과 간선을 그 지름에 중앙으로부터 멀어지는 방향으로 겹침으로써 선분 위에 모든 정점을 놓을 수 있다. 임의의 정점을 고르고, 그 정점에서 제일 먼 정점을 찾는다면 당연히 그 선분의 두 끝점 중 하나에 도달할 수밖에 없다. 따라서 그 선분의 끝점에서 다시 한번 제일 먼 점을 찾는다면, 그게 또 다른 지름의 끝점이 되어 문제가 풀리는 것이다.

 

고수들 사이에서는 나름 웰논일 것 같은데 나 같은 킹반인은 전혀 모르기 때문에 개념과 풀이 방법을 적어 보았다. 결론은 두 번만 탐색하면 된다는 것!

 

1197번 솔루션. 난잡하지만 일단 먹힌다.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;

#define INF 9999999
#define P pair<int, int>

int is_visited[100005] = {0};
vector<vector<P>> conn_list(100005);
vector<int> rand_list;
int sec_index_depth = 0, sec_index;

int dfs(int node, int depth){
    if(!is_visited[node]){
        is_visited[node] = true;
        int result = 0;
        for(P p : conn_list[node]){
            if(is_visited[p.first])
                continue;
            result = max(result, p.second + dfs(p.first, depth + p.second));
        }
        if(sec_index_depth < depth){
            sec_index_depth = depth;
            sec_index = node;
        }
        return result;
    }
    return 0;
}

int main() {
    int n;
    cin >> n;
    
    srand(time(0));
    
    for(int i = 0; i < n; i++){
        int from, to, dist, term = 0;
        cin >> from;
        while(true){
            cin >> to;
            if(to == -1)
                break;
            term++;
            cin >> dist;
            conn_list[from].push_back({to, dist});
        }
        if(term == 1)
            rand_list.push_back(from);
    }

    int index = rand_list[rand() % rand_list.size()];

    //cout << "picked : " << index << '\n';
    //cout << dfs(index, 0) << '\n';
    dfs(index, 0);
    //cout << "picked : " << sec_index << '\n';
    memset(is_visited, 0, sizeof(is_visited));
    cout << dfs(sec_index, 0);
    
    return 0;
}