본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

[boj] 백준 1389 케빈 베이컨의 6단계 법칙

[문제]

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

 

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

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻

www.acmicpc.net

 

[풀이]

BFS로 분류되어 BFS로 풀었으나 Floyd-Warshall Algorithm을 이용하는 방법도 있다고 한다. 이게 더 쉬울 것 같은데 이렇게도 한 번 풀어봐야겠다..

bfs 코드를 그대로 이용하면 되는데, 연결된 다리의 누적합을 구해서 비교해야 하므로 connect 배열에 연결 다리 수를 저장하도록 했다.

 

[코드]

 

#include <iostream>
#include <queue>
#include <cstring>

using namespace::std;

int relation[101][101];
int connect[101];
int result[101];
bool visited[101];
int N, M; //유저의 수, 친구 관계의 수

void bfs(int v){
    queue<int> q;
    q.push(v);
    visited[v] = true;

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

        for(int i=1; i<=N; i++){
            if(relation[u][i]==1 && visited[i]==false){
                visited[i]=true;
                q.push(i);
                connect[i] = connect[u]+1;
            }
        }
    }
}

int main() {
    //케빈 베이컨 수가 가장 작은 사람 출력.
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        relation[a][b] = 1;
        relation[b][a] = 1;
    }

    for(int i=1; i<=N; i++){
        bfs(i);
        for(int j=1; j<=N; j++){
            result[i] += connect[j];
        }
        memset(visited, false, sizeof(visited));
        memset(connect, 0, sizeof(connect));

    }

    int min = result[1];
    int min_person = 1;
    for(int i=2; i<=N; i++){
        if(result[i]<min) {
            min = result[i];
            min_person = i;
        }
    }

    cout << min_person;

}