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

[문제]

1389번: 케빈 베이컨의 6단계 법칙 (acmicpc.net)

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

[문제 풀이]

플로이드-워셜 알고리즘을 이용해서 풀었다.

2차원 배열에 해당 문제에서 나오지 않는 큰 정수를 default로 만들어 둔 뒤

3중 for문(플로이드-워셜)을 이용해서 자기 자신은 0으로 만들고 나머지는 모두 최소 몇번을 진행하면 갈수 있는지 파악하였다.

[코드]

#include <iostream>
#include <vector>

using namespace std;

int board[101][101];

void floid(int n) {

    for(int k = 1;k<=n;k++) {
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(i == j){
                    board[i][j] = 0;
                }
                if(board[i][j] > board[i][k] + board[k][j]){
                    board[i][j] = board[i][k] + board[k][j];
                }
            }
        }
    }

    return;
}

void output(int n){
    for(int i = 1;i<=n;i++){
        for(int j =1;j<=n;j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
    return;
}

int main(){
    int n,m;
    cin>>n>>m;
    
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=n;j++){
            board[i][j] = 10000000;
        }
    }

    for(int i = 0;i<m;i++){
        int a,b;
        cin>>a>>b;
        board[a][b] = 1;
        board[b][a] = 1;
    }

    floid(n);

    int answer = 0;
    int temp = 1000000000;
    int temp_2 = 0;

    for(int i = 1;i<=n;i++){
        temp_2 = 0;
        for(int j = 1;j<=n;j++){
            temp_2 += board[i][j];
        }
        if(temp > temp_2){
            temp = temp_2;
            answer = i;
        }
    }

    cout<<answer<<endl;

    return 0;
}