[promgrammers] 가장 먼 노드

문제 링크입니다

🚀 [가장 먼 노드] Lv. 3 문제

먼저 그래프의 문제 임으로 그래프를 이루는 2차원 벡터를 선언하고 edge를 계산하여 그래프를 구현합니다.
1 번 노드에서의 거리를 저장하는 distance 벡터를 생성합니다.
bfs 너비 우선 탐색을 이용하여 그래프를 순회합니다.
max_element를 이용해 최대로 먼 노드의 거리를 구하고 이와 일치하면 count하여 문제를 해결합니다.

💎 전체 코드는 다음과 같습니다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
// 방문 순서.
void bfs(vector<vector<int> > adj, vector<int>& distance, int start){
    distance = vector<int>(adj.size(),-1);
    queue<int> q;
    distance[start] = 0;
    q.push(start);
    while(!q.empty()){
        int here = q.front();
        q.pop();
        for(int i=0; i<adj[here].size(); i++){
            int there = adj[here][i];
            if(distance[there] == -1){
                q.push(there);
                distance[there] = distance[here] + 1;
            }
        }
    }

}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> graph(n+1);

    for(int i=0; i<edge.size(); i++)
    {
        int from = edge[i][0];
        int to = edge[i][1];

        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    vector<int> distance;
    bfs(graph,distance,1);

    int MAXX = *max_element(distance.begin(), distance.end());
    for(int i=1; i<distance.size(); i++){
        if(distance[i] == MAXX){
            answer++;
        };
    }
    return answer;
}