[JAVA] 백준 #1389 케빈 베이컨의 6단계 법칙 문제 풀이 | Floyd Warshall 알고리즘

🔒 문제

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

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

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

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

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

---

🔎  풀이

해당 문제 풀이 전에 플로이드 와샬 알고리즘에 대한 이해가 중요합니다! 

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

정말 크게 삽질한 문제 ... 알고보니 플로이드 와샬 알고리즘을 사용하면 너무나도 간단한 문제였다.

플로이드 와샬 알고리즘은 relations[ i , j ] ? relations [ i , k ] + relations [ k , j ] 를 비교해서
전자가 더 작다면 값을 갱신하지 않고, 후자가 작다면 값을 후자 값으로 갱신하면 된다. 

 

자, 플로이드 와샬 알고리즘의 진행을 직접 표를 갱신해보면서 확인해보자.

우선 초기에 relations 2차원 배열을 초기화했을 때([1]) relations는 다음과 같다.

자기 자신 노드와의 단계는 0, 두 노드가 서로 직접 이어져 있다면 1, 그렇지 않은 경우에는 무한대 숫자인 INF로 초기화한다. 

 

자 그럼 여기서 K=1 일때를 살펴보자. 

세로 열은 i, 가로 행은 j라고 둔다면 i = k | j = k인 행열에 대해선 갱신할 필요가 없다(하늘색 부분). 어차피 값이 안바뀌기 때문.

그래서 i !=k && j !=k 인 부분만 갱신하면 된다. 또한 서로 이어져 있는 relation[i][j] == 1인 경우는 그 자체로 최솟값이므로 더 갱신할 필요 없으므로 값이 i !=k && j !=k면서 relation[i][j] == INF인 나머지 부분을 갱신해보자.

(하지만 코드 상에서는 이런 예외처리를 생각할 필요가 없다!!)

 

먼저 relations[2,4]를 갱신해보자.

relations[2,4]와 relations[2,1] + relations[1,4] 두 개를 비교해보면, 전자는 INF 후자는 INF + 1 이므로 둘다 무한대 값이다. 그러므로 갱신이 일어나지 않고 그대로 INF. 또한 친구 관계는 양방향 관계이므로 relations[2,4] = relations[4,2]이다.

 즉, 대각선 기준으로 위쪽만 채우면 아래쪽은 위쪽과 대응되는 곳에 같은 값을 적으면 된다.

 

다음 relations[2,5]를 보자.

relations[2,5]와 relations[2,1] + relations[1,5]를 비교하면, 전자는 INF 후자는 INF + INF 이므로 여기서도 갱신이 일어나지 않는다. 

 

사실, 이번 예제에 대해서 k=1, k=2까지 어떠한 갱신도 일어나지 않는다. 유의미한 갱신은 k=3일때 발생하는데 이 경우를 같이 살펴보자.

k=3일때 갱신해야할 부분은 아래와 같다(파란색 부분과 값이 0,1 인 부분을 제외한 나머지). 

 여기서 relations[1,2]( = relations[2,1] )를 갱신해보자.

relations[1,2]와 relations[1,3] + relations[3,2]를 비교하면, 전자는 INF 후자는 1 + 1 이므로 후자인 2로 갱신이 발생한다!

 

이번에는 relations[2,4]( = relations[4,2] )를 갱신해보자.

relations[2,4]와 relations[2,3] + relations[3,4]를 비교하면, 전자는 INF 후자는 1 + 1 이므로 후자인 2로 갱신이 발생한다!

 

k = 3일 때 드디어 갱신이 발생했는데 모든 갱신을 처리한 뒤 relations 배열은 다음과 같이 변한다.

 

같은 방법으로 k = 4를 실행하면 표의 나머지 INF 값에 모두 갱신이 일어나 relations가 최종값을 가지게 된다. (k=5를 실행할 필요 없음)

 

그럼 이제 각 유저의 케빈 베이컨 수를 구해보자. 

유저 1: 0 + 2 + 1 + 1 + 2 = 6

유저 2: 2 + 0 + 1 + 2 + 3 = 8

유저 3: 1 + 1 + 0 + 1 + 2 = 5

유저 4: 1 + 2 + 1 + 0 + 1 = 5

유저 5: 2 + 3 + 2 + 1 + 0 = 8

 

그러므로 최솟값을 가지면서 번호가 가장 작은 유저는 3이다.

 

코드를 직접 확인해보자.

import java.util.Scanner;

public class Main {
    static int[][] relations;
    static int[] kevinBaconQuotient;
    static final int INF = 9999999;

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();    // 유저의 수
        int M = in.nextInt();    // 친구 관계의 수

        relations = new int[N][N];
        kevinBaconQuotient = new int[N];

        /***** [1]relations 배열 초기화 *****/     
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < N; j++ ){
                if( i == j ) relations[i][j] = 0;
                else relations[i][j] = INF;
            }
        }

        for (int i = 0; i < M; i++) {       // 주어진 친구 관계를 바탕으로 친구 리스트 채우기
            int a = in.nextInt();
            int b = in.nextInt();

            relations[a-1][b-1] = 1;
            relations[b-1][a-1] = 1;
        }       
	/*******************************/
        
        
        /**** [2]플로이드와샬 알고리즘 구현부 ****/
        for(int k = 0; k < N; k++ ){     
            for( int i = 0; i < N; i++){
                for( int j = 0; j < N; j++){
                    if( relations[i][j] > relations[i][k] + relations[k][j] ){
                        relations[i][j] = relations[i][k] + relations[k][j];
                    }
                }
            }
        }
        /******************************/
        
        
	/**** [3]케빈베이컨 지수 구하기 ****/
        for( int i = 0; i < N; i++){
            int sum = 0;
            for( int j = 0; j < N; j++){
                sum += relations[i][j];
            }
            kevinBaconQuotient[i] = sum;
        }

	/**** [4]가장 작은 지수 같는 사용자 구하기 ****/	
        int minIndex = N + 1;
        int minKevinBacon = INF;
        for( int i = 0; i < N; i++ ){
            if( kevinBaconQuotient[i] < minKevinBacon ) {
                minKevinBacon = kevinBaconQuotient[i];
                minIndex = i + 1;
            }
        }
        System.out.println(minIndex);
    }
}

표로 그렇게 복잡하게 풀이했는데 막상 코드는 3중 for문에 조건문 하나로 끝 ... ^^ 알고보면 매우매우 간단하다

플로이드와샬 알고리즘의 장점은 이렇게 코드가 간결하고 직관적인 것, 하지만 단점은 시간 복잡도가 무려  n의 세제곱이다.