[Programmers] 가장 먼 노드

[Programmers] 가장 먼 노드

Problem URL : 가장 먼 노드

#include <string>
#include <vector>
#include <queue>
#define INF 1e9

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> adj;
    vector<int> dist;
    adj.resize(n + 1);
    dist.resize(n + 1);
    fill(dist.begin(), dist.end(), INF);
    int size = edge.size();
    for(int i = 0; i < size; i++) {
        adj[edge[i][0]].push_back(edge[i][1]);
        adj[edge[i][1]].push_back(edge[i][0]);
    }
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        int size = adj[now].size();
        for(int i = 0; i < size; i++) {
            if(dist[adj[now][i]] > dist[now] + 1) {
                dist[adj[now][i]] = dist[now] + 1;
                q.push(adj[now][i]);
            }
        }
    }
    
    int maxDist = 0;
    for(int i = 2; i <= n; i++) {
        if(maxDist == dist[i]) {
            answer++;
        }
        if(maxDist < dist[i]) {
            maxDist = dist[i];
            answer = 1;
        }
    }
    
    return answer;
}