[BOJ] 1389 케빈 베이컨의 6단계 법칙

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

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

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

floyd-warshall algorithm

 

---------------------------------------------------풀이----------------------------------------------------

 

각 user가 연결되어 있으면 cost가 1이고, 이를 인접 행렬에 저장한다.

자기 자신끼리는 cost가 0이고, 연결되어 있지 않으면 99999999이라는 큰 값을 임의로 저장하였다.

그 다음, 플로이드-워셜 알고리즘을 적용해 모든 user에서 모든 user까지의 cost를 구해준다.

시작 유저 i에서 도착 유저 j까지 이동할 때, 유저 k를 거쳐 갈 경우의 cost와 비교해 업데이트 하는 방식이다.

즉, cost[i][j] = min(cost[i][k]+cost[k][j])를 모든 점에 대해 업데이트하며 반복한다.

이렇게 구한 값을 이용해 시작 유저가 0~N-1일 때 도착 유저들까지의 cost의 합을 구해 최소를 가지는 유저를 출력한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int users[101][101] = {0, };

// 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산.
// 모든 사람과 이 게임을 했을 때 나오는 단계의 합이 가장 작은 사람. 그중 번호가 가장 작은사람=?
int main(void){
    FASTIO;
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i == j){
                continue;
            }
            users[i][j] = 99999999;
        }
    }
    int u1, u2;
    for(int i = 0; i < M; i++){
        cin >> u1 >> u2;
        users[u1-1][u2-1] = 1;
        users[u2-1][u1-1] = 1;
    }

    // floyd warshall - 모든 정점에서 모든 정점까지의 최단경로 구하기
    for(int k = 0; k < N; k++){ // 거쳐가는 정점
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(users[i][k]+users[k][j] < users[i][j]){
                    users[i][j] = users[i][k]+users[k][j];
                }
            }
        }
    }

    int min = INT_MAX;
    int min_user = 0;
    // 합이 가장 작은 사람 찾기
    for(int i = 0; i < N; i++){
        int sum = 0;
        for(int j = 0; j < N; j++){
            sum += users[i][j];
        }
        if(sum < min){
            min = sum;
            min_user = i+1; // 1번부터로 변경해 저장
        }
    }

    cout << min_user << "\n";

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

모든 점에서 모든 점까지 구한다는 점에서 플로이드-워셜 알고리즘을 착안했다.

처음 구현할 때 실수한 부분은, 연결 되지 않은 유저끼리의 cost를 INT_MAX로 설정한 것이다.

INT_MAX에 다른 값을 더하면 음수가 되므로 엉뚱한 값을 찾게 되었다.