Hueestory

[1167] 트리의 지름 (C++) 본문

PS(중단)/BOJ

[1167] 트리의 지름 (C++)

히명 2024. 5. 7. 13:26
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int max_cost = 0; int farthest = 1;
vector<pair<int, int>> A[100002];

void DFS(int start, int prev, int cost);

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

    int v; cin >> v;
    int a, b, c;

    for (int i = 0; i < v; i++) {
        cin >> a;
        while (1) {
            cin >> b;
            if (b == -1) break;
            cin >> c;
            A[a].push_back(make_pair(b, c));
        }
    }

    DFS(1, 0, 0);
    max_cost = 0;
    DFS(farthest, 0, 0);
    cout << max_cost;

    return 0;
}

void DFS(int start, int prev, int cost) {
    if (cost > max_cost) {
        max_cost = cost;
        farthest = start;
    }

    for (int i = 0; i < A[start].size(); i++) {
        if (A[start][i].first != prev)
            DFS(A[start][i].first, start, cost + A[start][i].second);
    }
}

 

1. 루트 노드에서 가장 먼 두 노드 사이의 거리가 트리의 지름

2. 첫 번째 DFS에서 기본 루트를 1로 설정하고, 가장 먼 노드를 찾음

3. 두 번째 DFS에서는 2에서 찾은 노드를 기준으로 가장 먼 노드를 다시 탐색

4. max_cost에 두 노드 사이의 거리를 저장 후 출력

 

'PS(중단) > BOJ' 카테고리의 다른 글

[2343] 기타 레슨 (C++)  (0) 2024.05.13
[1920] 수 찾기 (C++)  (0) 2024.05.07
[2178] 미로 탐색 (C++)  (0) 2024.05.04
[1260] DFS와 BFS (C++)  (0) 2024.05.03
[1978] 소수 찾기 (C++)  (1) 2024.05.01
Comments