[c++] 트리의 지름(Tree Diameter)

12 Dec 2023

서론

트리의 지름이란 트리에서 가장 먼 두 정점 사이의 거리를 의미합니다. 이 글에서는 C++로 트리의 지름을 찾는 방법을 다루겠습니다.

알고리즘 개요

트리의 지름을 찾기 위해 다음 알고리즘을 사용할 것입니다.

임의의 정점을 선택한 후 가장 먼 정점을 찾습니다.
해당 정점으로부터 가장 먼 정점을 찾아 거리를 구합니다.

코드 예시

아래는 C++로 트리의 지름을 찾는 코드의 예시입니다.

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

vector<pair<int, int>> tree[100001]; // 각 정점마다 연결된 정점과 가중치
bool visited[100001];
int max_dist, max_node;

void bfs(int start) {
    queue<pair<int, int>> q;
    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        int cur_node = q.front().first;
        int cur_dist = q.front().second;
        q.pop();

        if (cur_dist > max_dist) {
            max_dist = cur_dist;
            max_node = cur_node;
        }

        for (auto next : tree[cur_node]) {
            int next_node = next.first;
            int next_dist = next.second;

            if (!visited[next_node]) {
                visited[next_node] = true;
                q.push({next_node, cur_dist + next_dist});
            }
        }
    }
}

int findTreeDiameter(int start) {
    max_dist = 0;
    max_node = 0;
    bfs(start);

    fill(visited, visited + 100001, false);

    max_dist = 0;
    bfs(max_node);

    return max_dist;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        tree[v1].push_back({v2, w});
        tree[v2].push_back({v1, w});
    }

    int diameter = findTreeDiameter(1);
    cout << "트리의 지름: " << diameter << endl;

    return 0;
}

결론

이제 여러분은 C++를 활용하여 트리의 지름을 찾는 방법을 알게 되었습니다. 이를 통해 트리 구조에서의 가장 먼 거리를 계산하는데 도움이 될 것입니다.

참고 자료

https://www.geeksforgeeks.org/diameter-tree-using-dfs/
https://en.wikipedia.org/wiki/Tree_(graph_theory)#Graph_dimension