[Algorithm] 백준 알고리즘 기초 2/2 - 트리의 지름

트리의 지름

트리에 존재하는 경로 중에서 가장 긴 것의 길이를 트리의 지름이라고 한다.

트리의 지름은 탐색 2번으로 구할 수 있다.

1. 한 정점 $s$에서 모든 정점까지의 거리를 구한다. 이 때, 가장 먼 거리의 정점을 $u$라고 한다.
2. $u$에서 모든 정점까지의 거리를 구한다. 이 때, 가장 먼 거리의 정점을 $v$라고 한다.

$d(u,v)$를 $u$와 $v$사이의 거리라고 할 때, $d(u, v)$가 트리의 지름이다.

증명

$d(u,v)$를 트리의 지름이라고 하자.

한 정점 $s$에서 가장 거리가 먼 정점을 $x$라고 하고 $x$에서 가장 거리가 먼 정점을 $y$라고 하자.

$wlog$(일반성을 잃지 않고) $d(s,u)\geq{d(s,v)}$이다. 이 때, 반드시 $d(s,x)\geq{d(s,y)}$는 반드시 성립해야 한다.

경로 $uv$에 포함되는 한 정점을 $z_{uv}$라고 하고, 경로 $xy$에 포함되는 한 정점을 $z_{xy}$라고 하자.

1. $d(z_{uv},y)\leq{d(z_{uv},v)}$

그렇지 않으면, 트리의 지름은 $d(u,y)$이므로 $d(u,v)\lt{트리의 지름}$ 이 된다.

2. $d(z_{uv},x)\leq{d(z_{uv},u)}$

그렇지 않으면, 트리의 지름은 $d(x,v)$이므로 $d(u,v)\lt{트리의 지름}$ 이 된다.

3. $d(s,z_{xy})+d(z_{xy},x)\geq{d(s,z_{uv})+d(z_{uv},u)}$

그렇지 않으면, $s$에서 가장 거리가 먼 정점이 $x$라는 가정이 거짓이 된다.

4. $d(z_{xy},y)\geq{d(v,z_{uv})+d(z_{uv},z_{xy})}$

그렇지 않으면, $x$에서 가장 거리가 먼 정점이 $y$라는 가정이 거짓이 된다.

1과 2에 의해

$d(u,v)=d(z_{uv},v)+d(z_{uv},u)\geq{d(z_{uv},x)+d(z_{uv},y)}=d(x,y)+2\times{d(z_{xy},z_{uv})}\geq{d(x,y)}$

3과 4에 의해

$d(z_{xy},y)+d(s,z_{xy})+d(z_{xy},x)\geq{d(v,z_{uv})+d(z_{uv},z_{xy})+d(s,z_{uv})+d(z_{uv},u)}$ $\because 3 + 4$

$d(x,y)=d(z_{xy},y)+d(z_{xy},x)\geq{d(v,z_{uv})+2\times{d(s,z_{uv})+d(z_{uv},u)}}\geq{d(u,v)}$ $\because d(s,z_{xy})=d(z_{uv},z_{xy})-d(z_{uv},s)$

$d(u,v)\geq{d(x, y)}$ 이고 $d(x,y)\geq{d(u,v)}$ 이므로 $d(u,v)=d(x,y)$

백준 1167번 - 트리의 지름

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

소스코드(C++)

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

struct Edge {
    int to;
    int cost;
    Edge(int to, int cost) : to(to), cost(cost) { }
};

vector<Edge> a[100001];
bool check[100001];
int dist[100001];

void bfs(int start) {
    memset(dist, 0, sizeof(dist));
    memset(check, false, sizeof(check));
    queue<int> q;
    check[start] = true;
    q.push(start);
    while(!q.empty()) {
        int x = q.front();    q.pop();
        for(int i = 0; i < a[x].size(); i++) {
            Edge &e = a[x][i];
            if(check[e.to] == false) {
                dist[e.to] = dist[x] + e.cost;
                q.push(e.to);
                check[e.to] = true;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while(true) {
            int y, z;
            cin >> y;
            if(y == -1) {
                break;
            }
            cin >> z;
            a[x].push_back(Edge(y, z));
        }
    }
    bfs(1);
    int start = 1;
    for(int i = 2; i <= n; i++) {
        if(dist[i] > dist[start]) {
            start = i;
        }
    }
    bfs(start);
    int ans = dist[1];
    for(int i = 2; i <= n; i++) {
        if(ans < dist[i]) {
            ans = dist[i];
        }
    }
    cout << ans << '\n';
    return 0;
}