백준 1167 트리의 지름 (C++)

1167번: 트리의 지름

dfs를 이용한 문제이다. 먼저 트리의 지름을 구하는 법에 대해 알아야 한다. 트리의 지름은 임의의 두 점의 거리 중 가장 긴 것을 말한다. 이를 공식화 해볼 수 있는데 아래와 같다.

1. 정점 x에서 가장 거리가 먼 정점 y를 구한다.
2. 정점 y에서 가장 거리가 먼 정점 z를 구한다.
3. 정점 y에서 정점 z까지의 거리를 구한다.

정점 y에서 정점 z까지의 거리가 트리의 지름이 된다. 이를 알고리즘에 적용해보자. 먼저 정점 1에서 dfs를 시작하여 가장 먼 거리의 정점 maxn을 구해주었다. 그 후 maxn에서 dfs를 시작하여 가장 긴 길이를 구해주었다. 처음 알게된 개념을 이용한 문제였다. 트리의 지름을 구하는 법을 알지 못해 반복문을 돌며 dfs를 이용해 가장 긴 거리를 구해줄려고 하니 시간 초과가 났었다. 이 후 지름을 구하는 공식을 찾아보고 빠르게 풀 수 있었다. 트리의 지름을 구하는 법에 대해 잘 알아두자.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int V;
vector<pair<int, int>> tree[100001];
bool check[100001];
int maxn, result = 0;

void dfs(int now, int sum) {
    for (int i = 0; i < tree[now].size(); i++) {
        int next = tree[now][i].first;
        int d = tree[now][i].second;

        if (check[next]) continue;

        check[next] = true;
        dfs(next, sum + d);
    }

    if (result < sum) {
        maxn = now;
        result = sum;
    }
}

void solution() {
    check[1] = true;
    dfs(1, 0);

    memset(check, 0, sizeof(check));

    check[maxn] = true;
    dfs(maxn, 0);

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> V;

    for (int i = 1; i <= V; i++) {
        int a, b, c, j = 0;

        cin >> a;

        while (1) {
            if (j % 2 == 0) {
                cin >> b;
                if (b == -1) break;
            }
            if (j % 2 == 1) {
                cin >> c;
                tree[a].push_back({ b,c });
            }
            j++;
        }
    }

    solution();

    return 0;
}