[BOJ 1167] 트리의 지름

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

1167번: 트리의 지름

Tag : tree dp

 

문제요약

트리에서 가장 먼 정점쌍을 찾고 거리를 출력해라.

 

풀이

두가지 풀이가 존재한다. 

 

1. 탐색 두번

음수 가중치를 가진 간선이 없을 때 성립하는 풀이로 아무 정점에서나 한번 돌려서 가장 먼 점을 찾고

찾은 가장 먼점에서 또 가장 먼 점을 찾는 풀이이다.

트리를 펼친 그림 (hgmhc님 블로그에서 가져왔습니다)

위 그림을 보면 아무 정점에서나 먼점을 찾아도 그게 바로 지름의 한쪽 끝이 된다는걸 알 수 있다.

 

전체코드

vpi v[101010];
ll mx = 0, mi = 0;
int n;
int check[101010];

void dfs(int here, ll d){
    if(d > mx) mx = d, mi = here;
    check[here] = 1;
    for(auto i : v[here]){
        if(check[i.first]) continue;
        dfs(i.first,i.second + d);
    }
}

#define io cin.tie(0)->sync_with_stdio(0)

int main() {
    io;
    cin>>n;
    for(int i =0 ; i<n; i++){
        int a; cin>>a;
        while(1){
            int to, w;
            cin>>to;
            if(to == -1) break;
            cin>>w;
            v[a].pb({to, w}), v[to].pb({a, w});
        }
    }
    dfs(1, 0);
    int st = mi;
    mx = 0;
    memset(check, 0, sizeof check);
    dfs(mi, 0);
    cout<<mx;

    return 0;
}

---

2. 트리 dp

dp[i] = i의 서브트리에 속하는 정점 중 가장 먼 점과의 거리

dp[i] = max(dp[nxt] + (i->nxt간선의 가중치))

이 dp값을 통해 정점마다 자신을 지나는 최대 길이를 구하면 지름을 구할 수 있다.

 

+ 트리 dp 풀이는 구현이 빡세다는 얘기를 들은 적이 있어서 안해봤었는데 왜 구현이 쉬운거지...?

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n, ans = 0;
int dp[101010]; // dp[i] = i에서 서브트리에서 i랑 가장 먼 점
vector<pair<int, int>> v[101010];

void dfs(int x, int p) {
    int mx = 0;
    for(auto &[i, j] : v[x]) if(i != p) {
        dfs(i, x);
        ans = max(ans, mx + dp[i] + j);
        mx = max(mx, dp[i] + j);
        dp[x] = max(dp[x], dp[i] + j);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n;
    for(int i=1; i<=n; i++) {
        int x; cin >> x;
        int a, b;
        while(1) {
            cin >> a;
            if(a == -1) break;
            cin >> b;
            v[x].push_back({a, b});
        }
    }
    dfs(1, 0);
    cout << ans << endl;
}