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

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

1967번: 트리의 지름

https://minuuu.tistory.com/62

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

위와 동일한 문제이다. 풀이 또한 같지만 알고리즘은 스택을 사용해서 구현했다.

풀이

최장 거리 경로는 유일하기 때문에, 임의의 정점에서 가장 멀리 있는 노드를 찾으면 전체 트리에서 최장 경로를 형성하는 두 노드 중 하나로 연결된다. 따라서, 두번의 DFS를 통해 전체 트리에서 최장 거리를 구할 수 있다.

1. DFS 를 사용해서 임의의 정점에서 가장 멀리 있는 정점을 찾는다.

2. dist 벡터를 -1로 초기화해, 아직 방문하지 않은 노드를 -1, 방문한 노드는 거리로 업데이트 한다.

3. 그 정점에서 다시 가장 멀리 있는 정점을 찾았을 때의 거리가 전체 트리에서 최장 거리이다.

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n, parent, child, weight;

struct Node
{
    int vex, weight;
    Node(int a, int b){
        vex=a;
        weight=b;
    }
};

pair<int, int> dfs(vector<vector<Node>>& g, int st)
{
    stack<int> stk;
    vector<int> dist(n+1, -1);
    stk.push(st);   
    dist[st]=0;
    
    while (!stk.empty()){
        int v = stk.top();
        stk.pop();
        
        for (int i=0; i<g[v].size(); i++){
            int nv = g[v][i].vex;
            int nc = g[v][i].weight;
            if (dist[nv]==-1){
                dist[nv] = dist[v]+nc;
                stk.push(nv);
            }
        }
    }
    int max_idx=0;
    int max=0;
    for (int i=1; i<dist.size(); i++){
        if (dist[i]>max){
            max = dist[i];
            max_idx=i;
        }
    }

    return {max_idx, max};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("input.txt", "r", stdin);
    cin >> n;
    vector<vector<Node>> graph(n+1);
    for (int i=0; i<n; i++){
        cin >> parent >> child >> weight;
        graph[parent].push_back(Node(child, weight));
        graph[child].push_back(Node(parent, weight));
    }

    pair<int, int> v;
    v = dfs(graph, 1);
    v = dfs(graph, v.first);
    cout << v.second << endl;
    return 0;
}