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

문제 설명

 

 

=> BFS문제입니다. 

=> 각 노드들이 맺고 있는 관계들을 벡터로 표현하였습니다. 

=> 이를 vector로 표현하거나 배열로 하거나 편하신대로 하면 됩니다. 

=> 해당 문제에서는 노드의 개수와 간선의 개수가 20,000개 , 50,000개 이므로 벡터를 사용하여 공간의 낭비를 줄였습니다. 

=> 간선들을 표현한 이후에는 항상 사용하던 BFS를 사용하여 문제를 해결하였습니다. 

https://codingham.tistory.com/168

DFS, BFS code

 

BFS CODE 예제입니다. 

 

 

#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;
}