백준 6118 - 숨바꼭질 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/6118

풀이전략

1. 1에서 가장 멀리떨어진 곳을 찾으면 된다. 기존에 했던것과 동일하게 1에서 부터 시작하여 모든 정점들로 BFS를 하여 최대값을 찾으면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
bool ch[50001];
vector<int> graph[50001];

int dist[50001];

int BFS(int start){
    int res = 0;
    ch[start] = true;
    queue<pair<int, int> >q;
    q.push(make_pair(start,0));

    while(!q.empty()){
        int v = q.front().first;
        int dis = q.front().second;
        if(dis>res)res = dis;
        dist[v] = dis;
        q.pop();

        for(int i=0; i<graph[v].size(); i++){
            if(!ch[graph[v][i]]){
                ch[graph[v][i]] = true;
                q.push(make_pair(graph[v][i], dis+1));
            }
        }
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N >> M;
    int ta, tb;
    for(int i=1; i<=M; i++){
        cin >> ta >> tb;
        graph[ta].push_back(tb);
        graph[tb].push_back(ta);
    }

    int res = 0;
    res = BFS(1);
    int cnt = 0;
    for(int i=2; i<=N; i++){
        if(dist[i] == res){
            if(cnt == 0) cout<< i << " ";
            cnt++;
        }
    }
    cout << res << " " << cnt << endl;
    return 0;
}

소감

그냥 BFS문제이다.