[프로그래머스] 가장 먼 노드 c++

 

 

BFS풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
vector<vector<int>> v(50001); //간선벡터
bool visited[20001]; //방문여부
vector<int> dist(20001); //최단거리 저장 (dist[3]인 경우 3까지의 최단경로)
int max_dist; //최대거리
 
void bfs(int node){
    queue<int> q;
    visited[node] = true;
    q.push(node);
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i=0;i<v[x].size();i++){
            if(visited[v[x][i]])
                continue;
            dist[v[x][i]] = dist[x] + 1;
            q.push(v[x][i]);
            visited[v[x][i]] = true;
            max_dist = max(max_dist,dist[v[x][i]]);
        }
    }
    
}
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    for(int i=0;i<edge.size();i++){
        v[edge[i][0]].push_back(edge[i][1]);
        v[edge[i][1]].push_back(edge[i][0]);
    }
    
    visited[1] = true;
    bfs(1);
    
    for(int i=0;i<dist.size();i++){
        if(dist[i] == max_dist)
            answer++;
    }
    return answer;
}