(C++) - 백준(BOJ) 1389 : 케빈 베이컨의 6단계 법칙

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

1389번: 케빈 베이컨의 6단계 법칙

BFS로 푼 문제였습니다.

📕 풀이방법

📔 풀이과정

1. 사람을 정점, 사람관계를 간선으로 생각하면 그래프 형태로 간단히 나타낼 수 있습니다. 인접리스트 형태로 그래프를 입력받아 a에 저장해줍니다.

2. 모든 정점에 대해 for loop를 수행합니다.

 2-1. 이 후 bfs를 통해 각 정점부터 다른 이까지 도달할 때 거리를 d배열에 저장합니다.

 2-2. 이후 케빈 베이컨 수를 구해 ans에 저장해줍니다.

📔 정답출력

가장 작은 케빈 베이컨 수를 구해 출력해줍니다.

---

📕 Code

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
vector <int> a[101];
int c[101], d[101],ans[101],t=1000;
int n,m,u,v,sum;
void BFS(int p)
{
    queue <int> q;
    q.push(p);
    c[p] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < a[x].size(); i++)
        {
            int y = a[x][i];
            if (c[y] == 0)
            {
                q.push(y);
                c[y] = 1;
                d[y] = d[x] + 1;
            }
        }
    }
}
int main() {
    cin >> n >> m;
    while (m--)
    {
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        memset(c, 0, sizeof(c));
        memset(d, 0, sizeof(d));
        sum = 0;
        BFS(i);
        for (int j = 1; j <= n; j++)
        {
            sum += d[j];
        }
        ans[i] = sum;
    }
    for (int i = 1; i <= n; i++)
    {
        if (t > ans[i])
            t = ans[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (t == ans[i])
        {
            cout << i;
            break;
        }

    }
}