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

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

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 플로이드-워셜

 

문제 풀이

친구의 수(N)와 친구 관계의 수(M)이 주어진다.
그럼 친구 관계의 수를 받아 arr[friendOne][friendTwo] = 1, arr[friendTwo][friendOne] = 1 라고 저장해준다.

그럼 예제 입력 1을 입력 했을 때 다음과 같은 array가 완성될 것이다.

이 array를 가지고 array[i][j]일 때 i != j인 모든 칸을 채울 것이다.
채우는 방법은 간단하다. array[i][k] 와 array[k][j] 의 합은 array[i][j] 가 된다. 

 따라서 위의 그림같은 형식대로 문제가 풀릴 것이다.

 

코드 구현

#include <iostream>
using namespace std;

int friends[101][101] = {0};

int main(){
    int N, M; cin >> N >> M;

    int a, b;
    while(M--){
        cin >> a >> b;
        friends[a][b] = 1;
        friends[b][a] = 1;
    }

    bool check = true;
    int k, tmpValue;
    for(int cnt = 1; check; cnt++){
        check = false;
        for(int i=1; i<N+1; i++){
        for(int j=i+1; j<N+1; j++){
            if(friends[i][j] != 0) continue;
            tmpValue = INT32_MAX;
            for(k=1; k<N+1; k++){
                if(friends[i][k] == 0 || friends[k][j] == 0) continue;
                if(friends[i][k] > cnt || friends[k][j] > cnt) continue;

                tmpValue = min(tmpValue, friends[i][k] + friends[k][j]);
            }
            if(tmpValue == INT32_MAX) check = true;
            else friends[i][j] = tmpValue, friends[j][i] = tmpValue;
        }
        }
    }
    
    int answerIdx=0, answerValue = INT32_MAX, sum;
    for(int i=1; i<N+1; i++){
        sum = 0;
        for(int j=1; j<N+1; j++){
            sum += friends[i][j];
        }
        if(sum < answerValue){
            answerValue = sum;
            answerIdx = i;
        }
    } 

    cout << answerIdx;
}