[BOJ] 6118 숨바꼭질 c++

문제 링크

https://www.acmicpc.net/problem/6118

핵심 알고리즘

1번부터 시작하여 헛간의 거리를 dist배열에 저장한다.

이때 문제에서 길의 최소 개수가 거리이므로 bfs인 queue을 이용해야한다.

dist를 구할때마다 dist의 최대값을 계속 구한다.

최종적으로 dist의 최대값인 distance과 같은 dist개수와 처음 나온 index을 저장한 후, 출력한다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <sstream>
using namespace std;

vector<int> adj[20001];
int dist[20001];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        dist[i] = -1;

    queue<int> q;
    q.push(1);
    dist[1] = 0;
    int distance = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (auto nxt : adj[cur]) {
            if (dist[nxt] >= 0)
                continue;
            q.push(nxt);
            dist[nxt] = dist[cur] + 1;
            distance = max(distance, dist[nxt]);
        }
    }

    int cnt = 0, num = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == distance) {
            if (num == 0)
                num = i;
            cnt++;
        }
    }

    cout << num << " " << distance << " " << cnt;
}