[프로그래머스] 가장 먼 노드 (C++)

🔮문제

1번 노드로부터 가장 먼 노드 개수 return

 

n : 노드 수
edge : 간선정보

 

🔮풀이

bfs를 사용하여 1번 노드 ~ n번 노드와의 거리 dist 배열에 저장

 

🔮STL - sort
default = 오름차순 정렬

 

• sort(arr, arr+n);

• sort(v.begin(), v.end());

• sort(v.begin(), v.end(), compare);                //사용자 정의함수

• sort(v.begin(), v.end(), greater<자료형>());    //내림차순

• sort(v.begin(), v.end(), less<자료형>());        //오름차순  

---

🔮코드

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

using namespace std;

vector<vector<int>> arr(20001);
int visit[20001]={0};

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

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

    for(int i=1; i<=n; i++)
        sort(arr[i].begin(), arr[i].end());

    visit[1]=1;
    dist[1]=0;
    q.push(1);

    while(!q.empty()){
        int v=q.front();
        q.pop();

        for(int i=0; i<arr[v].size(); i++){
            int cur = arr[v][i];
            if(!visit[cur]){
                q.push(cur);
                visit[cur]=1;
                dist[cur]=dist[v]+1;
            }
        }
    }
    sort(dist.begin(), dist.end(), greater<int>());

    int _max = dist[0];

    for(auto x : dist){
        if(x == _max)
            answer += 1;
    }

    return answer;
}