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

프로그래머스: 가장 먼 노드

문제 링크

전형적인 BFS 문제였다. 1번 노드에서 BFS를 시작해서 단계가 진행될 때마다 거리를 1씩 늘려서 함께 저장하도록 한다.

풀이

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using pii = pair<int, int>;

bool visited[20001];
vector<int> graph[20001];

bool desc(int a, int b) {
    return a > b;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0, v, u, cnt;

    for(int i = 0; i < edge.size(); i++){
        u = edge[i][0]; v = edge[i][1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    queue<pii> q;
    vector<int> cnt_arr;
    visited[1] = true;
    q.emplace(pii(1, 0));
    cnt_arr.push_back(0);

    while(!q.empty()) {
        u = q.front().first;
        cnt = q.front().second;
        q.pop();
        for(int v : graph[u]) {
            if(visited[v]) continue;
            visited[v] = true;
            q.emplace(pii(v, cnt+1));
            cnt_arr.push_back(cnt+1);
        }
    }

    sort(cnt_arr.begin(), cnt_arr.end(), desc);

    int max = cnt_arr[0];

    for(int i = 0; i < cnt_arr.size(); i++) {
        if(cnt_arr[i] == max) answer++;
        else break;
    }

    return answer;
}