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

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
vector<int> parent;
vector<pair<int,int>> vv; // (노드, 1번노드부터의간선수)
 
int cnt=0;
 
int find_(int n){
    if(n == parent[n])
        return n;
    else{
        cnt++;
        int r;
        return r = find_(parent[n]);
    }
}
 
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int max_cnt=0;
    for(int i=0; i<=n; i++){
        parent.push_back(i);
    }
    
    for(int i=0; i<edge.size(); i++){
        if(edge[i][0]<edge[i][1]){ // 더 작은쪽으로 몰아주기위해
            if(parent[edge[i][1]] > edge[i][0]) // 원래있던 값보다 작을때만
                parent[edge[i][1]] = edge[i][0];
        }else{
            if(parent[edge[i][0]] > edge[i][1]) // 원래있던 값보다 작을때만
                parent[edge[i][0]] = edge[i][1];
        }
        
    }
    for(int i=1; i<=n; i++){ 
        cnt=0;
        find_(i); // 노드 하나씩 검사
        cout<<i<< "cnt : " << cnt << "\n";
        if(max_cnt < cnt) 
            max_cnt = cnt;
        vv.push_back({i, cnt});
    }
    for(int i=1; i<=n; i++){
        if(max_cnt == vv[i].second){
            answer++;    
        }
    }
    return answer;
}
 

---

다른사람코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

vector<vector<int>> adj;

struct A{
    int dist;
    int number;
    bool operator<(const A &o) const{
        return dist > o.dist;
    }
};

int bfs(int start){
    vector<bool> visited;
    priority_queue<A> pq;
    int n = adj.size();
    int max_dist = 0;
    int ans = 0;
    
    visited.resize(n+1, false); // n+1개인 false들
    
    pq.push({0, start});
    visited[start] = true; // 트루는 안와도 되도록
    
    while(!pq.empty()){
        A v = pq.top(); //??
        pq.pop();
        
        if(v.dist+1 > max_dist){
            max_dist = v.dist+1;
            ans = 1;
        }
        else if(v.dist+1 == max_dist){
            ans++;
        }
        for(auto node : adj[v.number]){
            if(!visited[node]){
                pq.push({v.dist+1, node});
                visited[node] = true;
            }
        }
    }
    return ans;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int m = edge.size();
    
    adj.resize(n+1);
    for(int i=0; i<m; ++i){
        int a = edge[i][0];
        int b = edge[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    answer = bfs(1);
  
    return answer;
}