[Silver 1] 1389번 케빈 베이컨의 6단계 법칙

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

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

 

이 문제는 BFS를 사용해서 해결할 수 있다.

 

알고리즘은 다음과 같다.

1. 1 번부터 N 번까지 BFS를 수행한다. 

2. BFS를 위한 queue는 친구인 번호와 이동한 횟수를 저장한다.

3. queue에 저장할 때 케빈 베이컨 수를 증가시킨다.

4. 케빈 베이컨 수가 최소인 사람의 번호를 저장한다.

 

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int N, M;
int arr[101][101];
bool visited[101];
int answer = 0;
int cavin = 987654321;

int bfs(int target, int goal){
    queue<pair<int,int>> q;
    q.push({target,0});
    visited[target] = true;

    while(!q.empty()){
        int go = q.front().first;
        int num = q.front().second;
        q.pop();
        if(go == goal){
            return num;
        }
        for(int i = 1;i<=N;i++){
            if(arr[go][i] && !visited[i]){
                q.push({i,num + 1});
                visited[i] = true;
            }
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N>>M;
    int go, to;
    for(int i = 0;i<M;i++){
        cin>>go>>to;
        arr[go][to] = 1;
        arr[to][go] = 1;
    }

    for(int i = 1;i<=N;i++){
        int temp = 0;
        for(int j = 1;j<=N;j++){
            if(j==i)
                continue;
            
            memset(visited,false,sizeof(visited));
            temp += bfs(i,j);
        }
        if(cavin > temp){
            cavin = temp;
            answer = i;
        }
    }

    cout<<answer<<'\n';
}