백준 1967번 [트리의 지름](C++) -yes6686- 티스토리

백준 문제 풀이: 1967 [트리의 지름]

---

문제 링크: https://www.acmicpc.net/problem/1967

문제 설명:

트리에서 두 노드 사이의 경로 중 가장 긴 경로를 구하는 문제입니다. 이 경로를 트리의 지름이라고 합니다.

입력:

• 첫째 줄에 노드의 개수 n이 주어집니다. (1 ≤ n ≤ 10,000)
• 다음 n-1개의 줄에는 트리의 간선 정보 a, b, c가 주어집니다. 이는 노드 a와 b가 가중치 c로 연결되어 있음을 나타냅니다.

출력:

• 트리의 지름을 출력합니다.

---

문제 해결 코드

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

vector<pair<int, int>> tree[10001]; // 트리의 인접 리스트 (노드, 가중치)
bool visited[10001]; // 방문 여부
int maxDist = 0; // 최대 거리
int farthestNode = 0; // 가장 먼 노드

// DFS를 사용하여 가장 먼 노드를 찾는 함수
void dfs(int node, int dist) {
    visited[node] = true;

    if (dist > maxDist) {
        maxDist = dist;
        farthestNode = node;
    }

    for (auto &edge : tree[node]) {
        int nextNode = edge.first;
        int weight = edge.second;
        if (!visited[nextNode]) {
            dfs(nextNode, dist + weight);
        }
    }
}

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

    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }

    // 첫 번째 DFS: 임의의 노드(1번)에서 가장 먼 노드를 찾음
    fill(visited, visited + n + 1, false);
    dfs(1, 0);

    // 두 번째 DFS: 가장 먼 노드에서 시작하여 트리의 지름을 계산
    fill(visited, visited + n + 1, false);
    maxDist = 0;
    dfs(farthestNode, 0);

    cout << maxDist << '\n';

    return 0;
}

예제

입력:
5
1 2 3
1 3 2
2 4 4
2 5 6

출력:
12

입력:
3
1 2 2
1 3 4

출력:
6

---

코드 설명

• 핵심 알고리즘:
  • DFS를 두 번 수행하여 트리의 지름을 구합니다.
  • 첫 번째 DFS: 임의의 노드에서 가장 먼 노드를 찾습니다.
  • 두 번째 DFS: 첫 번째 DFS에서 찾은 노드에서 가장 먼 노드까지의 거리를 계산하여 트리의 지름을 구합니다.
• 구현 세부사항:
  • tree[node]: 각 노드와 연결된 노드와 가중치를 저장합니다.
  • dfs(node, dist): 현재 노드에서 가장 먼 노드를 탐색합니다.
• 시간 복잡도 분석:
  • DFS의 시간 복잡도: O(n)
  • 총 두 번의 DFS 수행: O(2n)
  • 전체 시간 복잡도: O(n)

---

결과

코드는 트리의 지름을 효율적으로 계산하며, 입력 크기 제한 내에서 적절히 작동합니다. 첫 번째 DFS와 두 번째 DFS를 활용하여 트리의 지름을 정확히 구합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!