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

문제 접근

BFS를 사용해서 풀었다.
입력을 vector 배열로 바꿨다.
queue를 사용해서, node와 거리를 pair로 넣고, 하나의 node가 모든 node를 search를 했다면, 현재 max의 크기와 비교를 해서 더 큰 것을 max에 저장해준다.

코드 구현(c++)

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

vector<int> node[20001];
bool check[20001];
int cnt[20001];
int maxNum = -1;

void bfs(){
    queue<pair<int, int> > q;
    q.push(make_pair(1,0));
    check[1] = true;
    while(!q.empty()){
        int n = q.front().first;
        int num = q.front().second;
        q.pop();
        for(int i = 0 ; i < node[n].size() ; i++){
            if(!check[node[n][i]]){
                q.push(make_pair(node[n][i], num + 1));
                check[node[n][i]] = true;
            }
        }

        maxNum = max(maxNum, num);
        cnt[num]++;

    }
}
int solution(int n, vector<vector<int> > edge) {
    int answer = 0;

    memset(cnt, 0, sizeof(cnt));
    memset(check, false, sizeof(check));

    for(int i = 0 ; i < edge.size() ; i++){
        node[edge[i][0]].push_back(edge[i][1]);
        node[edge[i][1]].push_back(edge[i][0]);
    }
    bfs();
    answer = cnt[maxNum];
    return answer;
}