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

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

1167번: 트리의 지름

#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;
        while(1)
        {
            cin >> v;
            if(v==-1) break; //-1을 입력해야 입력 종료
            cin >> 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;
}

1967번 문제와 입력 케이스만 다를 뿐 거의 유사한 문제인 것 같다.

1967번 문제의 난이도 기여 탭을 보니 1167번 문제와 사실상 똑같다고 하는 말들이 제법 많이 보여서 봤더니 확실히 거의 동일한 답안으로 정답이 가능했다.

 

가장 다른 점은 N의 범위이다.

1967번이 N의 범위가 훨씬 적어서 N^2의 풀이가 가능하므로 골드4고 1167번은 N^2풀이가 불가능하여 dfs()를 2번 돌려야하는 풀이를 떠올려야 하는에 이게 쉽지 않기 때문에 골드2인 것 같다.

 

풀이는 1167번 문제 풀이를 참고하면 된다.

https://blob-thinking.tistory.com/231

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