DFS/BFS

#include <string>
#include <vector>

using namespace std;
#define MAX 210000000

void dfs(int dist, int dest, int cost[], bool g[][20001], int vert) {
    if(dest == 1) {
        cost[dest] = 0;
    }
    //출발지가 1이 아니면, 이미 왔던 곳이라면 dist가 더 클 땐 pass
    else if(cost[dest] > dist) {
        cost[dest] = dist;
    }
    else 
        return;
    
    for(int i =1; i<=vert; i++) {
        if(g[dest][i] != true)
            continue;
        dfs(dist+1, i, cost, g, vert);
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    bool g[20001][20001] = {false, };
    int cost[20001] = {0, };
    int vert = n;
    
    for(int i=1; i<=n; i++) {
        cost[i] = MAX;
    }
    for(int i=0; i<edge.size(); i++) {
        g[edge[i][0]][edge[i][1]] =true;
        g[edge[i][1]][edge[i][0]] =true;
    }
    
    dfs(0, 1, cost, g , vert);
    
    int mx=0;
    for(int i=1; i<=vert; i++) {
        mx = cost[i] > mx? cost[i] : mx;
    }
    for(int i=1; i<=vert; i++) {
        if(cost[i] == mx)
            answer++;
    }
    return answer;
}

//BFS방식

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

using namespace std;
//#define MAX 210000000

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    queue<int> q;
    
    bool g[20001][20001] = {false, };
    int cost[20001] = {0, };
    bool visit[20001] = {false, };
    
    //일단 edge를 오름차순으로 정렬
    //내림차순은 sort(edge.begin(), edge.end(), greater<>());
    sort(edge.begin(), edge.end());
    
    for(int i=0; i<edge.size(); i++) {
        g[edge[i][0]][edge[i][1]] =true;
        g[edge[i][1]][edge[i][0]] =true;
    }
    
    int mx=0;
    //1부터 시작
    q.push(1);
    visit[1] = true;
    
    while(!q.empty()) {
        int vert = q.front();
        q.pop();
        
        for(int i=2; i<=n; i++) {
            if(g[vert][i] == true && visit[i] != true) {
                q.push(i);
                visit[i] = true;
                cost[i] = cost[vert] + 1;
                
                //최대값 갱신
                if(cost[i] > mx) {
                    mx = cost[i];
                }
            }
        }
    }
    
    for(int i=1; i<=n; i++) {
        if(cost[i] == mx)
            answer++;
    }
    
    return answer;
}