가장 먼 노드

https://programmers.co.kr/learn/courses/30/lessons/49189

BFS를 통해 거리를 dist에 저장한다.

dist[i] = 1번 노드에서 i번 노드로 가는 최단 경로의 길이(간선의 개수)

#include <iostream>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int dist[20002] = { 0, }, Max = 0;
 
vector<int> v[20002];
 
int BFS(int e)
{
    int ret = 0;
 
    queue<int> q;
 
    q.push(1);
 
    dist[1] = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int now = q.front();
 
            q.pop();
 
            for (auto i : v[now])
                if (dist[i] == -1)
                {
                    dist[i] = dist[now] + 1;
 
                    Max = max(Max, dist[i]);
 
                    q.push(i);
                }
        }
    }
 
    for (int i = 1; i <= e; i++)
        if (dist[i] == Max) ++ret;
 
    return ret;
}
 
int solution(int n, vector<vector<int>> edge) 
{
    memset(dist, -1, sizeof(dist));
 
    for (int i = 0; i < edge.size(); i++)
    {
        int from = edge[i].at(0), to = edge[i].at(1);
 
        v[from].push_back(to);
        v[to].push_back(from);        
    }
 
    return BFS(n);
}
 
int main(void)
{
    vector<vector<int> > v = {
        {3, 6},
        {4, 3},
        {3, 2},
        {1, 3},
        {1, 2},
        {2, 4},
        {5, 2}
    };
 
    cout << "답 = " << solution(6, v) << '\n';
 
    return 0;
}