[플로이드-와샬] 케빈 베이컨의 6단계 법칙(1389) (C++)

 

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

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

 

1. 문제 개요

 

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.

예를 들어, 1이 2와 아는 사이이고 2가 3과 아는 사이, 3과 4는 아는 사이이면 1과 4는 3단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다. 

케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

 

이 문제는 사람의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨 수가 가장 작은 사람을 구하는 프로그램을 작성한다.

 

 

2. 입출력

 

 

3. 문제 풀이

 

플로이드-와샬 알고리즘을 응용하는 문제.

플로이드-와샬 알고리즘은 모든 쌍 최단 경로를 구하는 알고리즘으로 반복문을 3번 중첩시키기만 하면 되기 때문에 구현이 굉장히 쉽다.

//플로이드 와샬 알고리즘
for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            D[i][j] = INF; //배열 안의 값을 무한대로 초기화
            
//그래프의 정보를 입력받아 배열에 저장한다.
            
 for(int K=1;K<=n;K++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) //K를 경유해 가는 경우가 더 빠르다면 갱신해준다.
                D[i][j] = min(D[i][j], D[i][K] + D[K][j]);

 

이와 같이 그래프의 간선의 가중치를 무한대로 초기화 한 다음, 그래프의 노드 간의 거리에 대한 정보를 입력받아 이차원 배열에 저장하고 3첩 반복문을 돌려주면 된다.

 

이 문제는 간선의 가중치가 존재하지 않고 단순히 친구 관계만 주어지기 때문에 모든 가중치를 1로 저장했다.

 

for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            D[i][j] = INF; //배열 안의 값을 무한대로 초기화
        
    for(int i=0;i<m;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        D[a][b] = 1;
        D[b][a] = 1;
    } //a와 b가 친구인 경우
    
    for(int K=1;K<=n;K++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) //K를 경유해 가는 경우가 더 빠르다면 갱신해준다.
                D[i][j] = min(D[i][j], D[i][K] + D[K][j]);

 

따라서 친구인 경우에는 두 노드 간의 가중치가 1, 아닐 경우에는 가중치가 무한대가 되게 된다.

이렇게 모든 노드 간의 최단 경로를 구한 다음, 각각의 노드의 자신을 제외한 다른 노드와의 최단 경로의 합을 구하여 일차원 배열에 저장해준다.

 

for(int K=1;K<=n;K++) {
        for(int i=1;i<=n;i++)
            ANS[K] += D[K][i];
        ANS[K] -= D[K][K]; //자신으로 가는 경로는 빼줌
}

 

마지막으로 이렇게 구한 케빈 베이컨 수들의 최솟값을 찾아 번호를 출력하기만 하면 된다.

 

int min = ANS[1];
int index = 1;
for(int i=2;i<=n;i++) {
    if(ANS[i] < min) {
        min = ANS[i];
        index = i;
    }
} //최소값을 구해줌
            
printf("%d\n",index);

 

 

4. 전체 코드

 

#include <algorithm>
#include <stdio.h>

using namespace std;
//플로이드 와셜 알고리즘

const int MAX = 101;
const int INF = 10001000;
int D[MAX][MAX]; //최단 경로 값을 저장하는 배열
int ANS[MAX];

int main(void)
{
    int n,m; //노드의 수, 간선의 수
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            D[i][j] = INF; //배열 안의 값을 무한대로 초기화
        
    for(int i=0;i<m;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        D[a][b] = 1;
        D[b][a] = 1;
    } //a와 b가 친구인 경우
    
    for(int K=1;K<=n;K++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) //K를 경유해 가는 경우가 더 빠르다면 갱신해준다.
                D[i][j] = min(D[i][j], D[i][K] + D[K][j]);
    
    for(int K=1;K<=n;K++) {
        for(int i=1;i<=n;i++)
            ANS[K] += D[K][i];
        ANS[K] -= D[K][K]; //자신으로 가는 경로는 빼줌
    }
    
    int min = ANS[1];
    int index = 1;
    for(int i=2;i<=n;i++) {
        if(ANS[i] < min) {
            min = ANS[i];
            index = i;
        }
    } //최소값을 구해줌
            
    printf("%d\n",index);
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!