[BOJ 1967번/C++] 트리의 지름

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

1967번: 트리의 지름

트리의 지름

풀이

무언가 엄청 큰 다른 방식을 요하는 문제인가... 싶었는데, 참으로 간단(?)하게도 DFS를 이용해서 쉽게 풀 수 있는 문제였다.

 

1. DFS를 이용해 1에서 가장 먼 거리에 있는 노드 n을 구한다.

2. DFS를 이용해 노드 n에서부터 가장 먼 거리에 있는 노드 m을 구한다.

3. 그 m까지의 거리가 트리의 지름이다.

 

DFS를 2번 이용해서 풀 수 있는 문제..

 

위 과정을 다르게 말하자면,

1에서 가장 먼 거리의 노드는, 각 서브 트리의 여러 리프(leaf) 노드들 중 하나이다. 가장 먼 리프 노드를 n이라고 한다.

n에서 다른 리프 노드들 중 가장 먼 리프 노드를 m이라고 한다.

n에서 m까지의 거리가 가장 긴 경로이다.

 

이것이 되는 이유는 다른 분들께서 이미 상세히 잘 설명을 해주셨기에.. 여기서는 생략..

 

#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;

vector<pair<int, int>> tree[10001];
vector<bool> visited;
int max_len = 0;
int max_node = 0;

void dfs(int node, int dist) {
    if (max_len < dist) {
        max_len = dist;
        max_node = node;
    }

    visited[node] = true;

    for (int i = 0; i < tree[node].size(); i++) {
        if (!visited[tree[node][i].first]) {
            dfs(tree[node][i].first, dist + tree[node][i].second);
        }
    }    
}

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

    int n;
    cin >> n;

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

    visited.assign(n + 1, false);
    dfs(1, 0);

    max_len = 0;

    visited.assign(n + 1, false);
    dfs(max_node, 0);

    cout << max_len << endl;

    return 0;
}