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

문제 설명

 

 

 

=> BFS를 사용해 각 노드로 가는 거리들을 구합니다. 

=> 내가 지금 갈 노드 = 이전 노드 + 1; 

=> 가장 멀리 있는 노드값을 answer에 반환합니다. 

 

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> graph(n+1);
    
    for(auto ed : edge)
    {
        int from = ed[0];
        int to = ed[1];
        
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    
    vector<int> dist(n+1, -1);
    queue<int> q;
    
    dist[1] = 0;
    q.push(1);
    int max =0;
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(auto i : graph[cur])
        {
            if(dist[i] == -1)//가본적이 없으면
            {
                dist[i] = dist[cur]+1;
                if(max < dist[i]) max = dist[i];
                q.push(i);
            }
        }
    }
    
    sort(dist.begin(),dist.end());
    for(auto k : dist)
    {
        if(max == k )answer++;
    }
    
    return answer;
}