백준 1967번 트리의 지름

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

 

입력으로 트리가 주어지면 트리의 지름(트리에서 임의의 두 점 사이의 거리 중 가장 긴 것)을 구하는 문제다.

트리의 지름을 구하는 방법은 다음과 같다.

 

1. 임의의 노드 u에서 가장 먼 노드 v를 찾는다.

2. 노드 v에서 다시 가장 먼 노드 w를 찾는다.

3. v와 w 사이의 거리가 트리의 지름이 된다.

 

위 방법을 바탕으로 BFS를 사용하여 트리의 지름을 구한다.

 

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

pair<int, int> bfs(int n, vector<vector<pair<int, int>>> adj){
    pair<int, int> distant;
    queue<pair<int, int>> q;
    bool visited[adj.size()]={0};
    q.emplace(n,0);
    visited[n]=true;

    while(!q.empty()){
        int curN=q.front().first;
        int curD=q.front().second;
        if(distant.second < curD) distant={curN, curD};
        q.pop();

        for(int i=0; i<adj[curN].size(); i++){
            int nextN=adj[curN][i].first;
            int nextD=curD+adj[curN][i].second;
            if(!visited[nextN]){
                q.emplace(nextN, nextD);
                visited[nextN]=true;
            }
        }
    }
    return distant;
}

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

    int n, v1, v2, w;
    cin >> n;
    vector<vector<pair<int, int>>> adj(n+1);
    for(int i=0; i<n-1; i++){
        cin >> v1 >> v2 >> w;
        adj[v1].emplace_back(v2, w);
        adj[v2].emplace_back(v1, w);
    }

    pair<int, int> node1 = bfs(1, adj);
    pair<int, int> node2 = bfs(node1.first, adj);
    cout << node2.second;
    
    return 0;
}

 

입력을 받아 인접행렬을 만들때 pair<노드번호, 가중치> 형식을 사용했다.

bfs 함수도 노드번호와 거리를 반환하게 하여 두번의 bfs를 돌려 답을 구한다.