[백준 1967번] 트리의 지름 (C++)

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

1967번: 트리의 지름

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii>vec[100001];
bool visited[100001];
int result, target;

void dfs(int idx, int dist)
{
    visited[idx] = 1;
    if(result < dist)
    {
        result = dist; //가장 먼 거리 저장
        target = idx; //가장 먼 지점 저장
    }

    for(int i=0; i<vec[idx].size(); i++)
    {
        auto[next, ncost] = vec[idx][i];
        if(visited[next]) continue;
        dfs(next, ncost + dist);
    }
}

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

    int N;
    cin >> N;

    for(int i=0; i<N-1; i++)
    {
        int u, v, cost; //부모, 자식, 가중치
        cin >> u >> v >> cost;
        vec[u].push_back({v, cost});
        vec[v].push_back({u, cost});
    }

    dfs(1, 0); //가장 먼 위치 구하기
    memset(visited, 0, sizeof(visited)); //재탐색을 위해 초기화
    dfs(target, 0); //가장 먼 위치에 대해 가장 먼 거리 구하기 (지름 구하기)
    cout <<result;
    
    return 0;
}

dfs 탐색을 2번 돌리는 문제이다.

처음에는 시작 점으로부터 가장 먼 위치를 먼저 구한다.

어느 위치에서 시작해도 상관없으며 이렇게 구한 가장 먼 위치가 양 쪽 지름 중의 하나가 된다.

 

그러고 나서 방금 구한 위치를 기준으로 다시 dfs를 돌려서 가장 먼 거리를 구한다.

당연하게도 지름의 양 끝이 서로 가장 멀기 때문에 이렇게 구한 값이 지름의 길이가 된다.

<예제>
위치 1에서 시작이라고 가정
가장 먼거리 위치 9 (2 + 11 + 15 = 28)

9에서 다시 탐색 시작
가장 먼거리 위치 12 (15 + 11 + 9 + 10 = 45)

다른 사람들의 풀이를 살펴보니 대부분 비슷하게 푼 것 같다.

근데 해당 문제가 N의 범위가 크지 않아서  모든 정점에 대해 전부 확인하는 방법인 N^2으로도 풀리는 것을 볼 수 있었다.