숨바꼭질

---

문제풀이

비효율적이지 않은 동선으로 가장 먼지점을 구하면 모두다 구할수 있다.
따라서 BFS를 사용했다 (DFS는 가장 효율적인 동선을 선택하지 않는다.)
BFS를 쓰는 가장 전형적인 유형이다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
#define endl "\n"

#define MAX 50000+1
int n,m;
vector<int> graph[MAX];
int map[MAX];

void bfs(int _start ){ // 무조건 1부터 시작
    map[_start]= 1 ;
    
    queue<int> q;
    q.push(_start);
    while (!q.empty()) {
        int w = q.front();
        q.pop();
        
        for(auto v : graph[w]){
            if (!map[v]) {
                map[v] = map[w]+1;
                q.push(v);
            }
        }
    }
}


int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    //ifstream cin; cin.open("test.txt");
    
    cin>>n>>m;
    
    for (int i=0; i<m; i++) {
        int x,y;
        
        cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    bfs(1);
    
    int valueMax=0;
    for (int i=1; i<=n; i++) {
        if (valueMax<map[i]) {
            valueMax=map[i];
        }
    }
    int cnt=0;
    int firstNode=n;
    for (int i=1; i<=n; i++) {
        if (valueMax==map[i]) {
            cnt++;
            if (firstNode>=i) {
                firstNode=i;
            }
        }
    }
    
    cout<<firstNode<<' '<<valueMax-1<<' '<<cnt;


    return 0;
}