프로그래머스 (Programmers) 가장 먼 노드

BFS 이용해서 풀었다.

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
bool visited[20001];
vector<int> link[20001];
struct _pair {
    int num;
    int cnt;
};
queue<_pair> que;
int maxCnt = 0;
int solution(int n, vector<vector<int>> edge) {
    int answer = -1;
    int edgeN = edge.size();
    for (int i = 0; i < edgeN; i++) {
        int a = edge[i][0];
        int b = edge[i][1];
        link[a].push_back(b);
        link[b].push_back(a);
    }
    visited[1] = true;
    que.push({ 1, 0 });
    while (!que.empty()) {
        _pair pair = que.front();
        que.pop();
        if (pair.cnt > maxCnt) {
            maxCnt = pair.cnt;
            answer = 1;
        }
        else if (pair.cnt == maxCnt) {
            answer++;
        }
        for (int i = 0; i < link[pair.num].size(); i++) {
            int a = pair.num;
            int b = link[a][i];
            if (visited[b]) continue;
            visited[b] = true;
            que.push({ b,pair.cnt + 1 });
        }
    }
 
    return answer;
}