[BOJ] 1389 케빈 베이컨의 6단계 법칙 c++

문제 링크

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

핵심 알고리즘

인접 리스트 연습에 좋은 문제

친구면 양방향이므로 각 배열에 추가한다.

bfs로 dist배열에 케빈 베이컨 수를 구한다.

dist배열에 담긴 수를 모두 더해 앞의 베이컨 수와 비교하여 작으면 해당 유저의 번호를 따로 저장한다.

dist배열이 queue을 실행할 때마다 초기화되어야한다.

최종 코드

#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[101];
int dist[101];

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);
    }

    int bacon = 500000, ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            dist[j] = -1; //초기화

        queue<int> q;
        q.push(i);
        dist[i] = 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;
            }
        }

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

        if (bacon > sum) {
            bacon = sum;
            ans = i;
        }
    }

    cout << ans;
}