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

기본적인 BFS 문제이다.

문제 유형에 '플로이드 와샬 알고리즘'이 있어서, 쫄았다.(?)

(배웠긴 했지만, 까먹었기 때문이다. 꼭 다음 주 내로 각종 알고리즘들을 복습해야겠다.)

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, M = 0;
 
int s = 0, e = 0;
 
vector<vector<int> > v;
 
int BFS(int start)
{
    int ret = 0;
 
    for (int index = 1; index <= N; index++)
    {
        bool stop = false;
 
        if (start != index)
        {
            queue<int> q;
 
            bool visit[102] = { false, };
 
            q.push(start);
 
            while (!q.empty())
            {
                int qSize = q.size();
 
                while (qSize--)
                {
                    int here = q.front();
 
                    q.pop();
 
                    if (here == index)
                    {
                        stop = true;
                    }
 
                    if (visit[here]) continue;
 
                    visit[here] = true;
 
                    for (int next : v[here])
                    {
                        if (!visit[next])
                        {
                            q.push(next);
                        }
                    }
                }
 
                if (stop) break;
 
                ++ret;
            }
        }    
    }
 
    return ret;
}
 
int main(void)
{
    int ans = 987654321;
 
    scanf("%d %d", &N, &M);
 
    v.resize(N + 1);
 
    while (M--)
    {
        scanf("%d %d", &s, &e);
 
        v[s].push_back(e);
        v[e].push_back(s);
    }
 
    int min_index = 0;
 
    for (int i = 1; i <= N; i++)
    {
        int var = BFS(i);
 
        if (ans > var)
        {
            ans = var;
            min_index = i;
        }
    }
 
    printf("%d\n", min_index);
 
    return 0;
}