C++:: 프로그래머스 < 가장 먼 노드 >

그래프를 구현하는데 주어진 노드의 개수가 20000개 정도로 적기 때문에 이중벡터로 구현해도 된다.

#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int solution(int n, vector<vector<int>> edge) {
    vector<vector<int>> nodes(20001);
    vector<int> vis(n+1, 0);
    deque<int> dq(1, 1);
    vis[0] = 0, vis[1] = 1;
    for (auto& e : edge) {// 간선 등록
        nodes[e[0]].push_back(e[1]);
        nodes[e[1]].push_back(e[0]);
    }
    while (!dq.empty()) {
        int cur = dq.front();
        dq.pop_front();
        for (auto& idx : nodes[cur]) {
            if (vis[idx]) continue;// 이미 방문한 적 있다면
            vis[idx] = vis[cur]+1;
            dq.push_back(idx);
        }
    }
    sort(vis.begin(), vis.end());//정렬
    return vis.end() - max_element(vis.begin(), vis.end());
}