[백준 1389번] 케빈 베이컨의 6단계 법칙-JAVA

문제 링크

문제

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

 

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

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

 

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

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

 

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

 

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

 

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

 

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

 

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

 

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

 

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

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

---

접근 방법

그래프 탐색을 통해 모든 노드 간의 거리를 계산하고 케빈 베이컨 수가 가장 적은 사람을 출력한다.

조건

• 모든 노드는 연결되어 있다.
• 단계를 거칠수록 가중치 값은 늘어난다.
• 케빈 베이컨 수가 적은 사람이 중복될 경우 번호가 가장 작은 사람을 출력한다.

 

백준에서 제공하는 알고리즘 분류를 확인하면 그래프 이론, 그래프 탐색, 너비 우선 탐색, 플로이드-워셜로 구분되고,

여기서는 플로이드-워셜을 통해 문제를 해결한다.

Floyd-Warshall 알고리즘 이란?

1. 모든 노드 간에 최단거리를 구하는 알고리즘이다.
2. 다익스트라, 벨만포드는 한 노드에서 모든 노드까지의 최단 경로를 구하는 알고리즘이지만
   Floyd-Warshall은 모든 노드에서 모든 노드까지의 최단 경로를 구하는 알고리즘이다.
3. 벨만포드와 마찬가지로 가중치에 음수가 있어도 가능하다.
4. 3중 for문을 사용하기 때문에 시간 복잡도는 를 갖는다.

주어진 예제를 통해 깊이 있게 학습해 보자 먼저 주어진 친구 관계를 그래프로 나타내면 아래와 같고, 단계를 거칠수록 가중치가 높아지기

때문에 친구 관계인 노드 간의 이동은 1, 친구를 통해 연결된 노드로 이동하는 경우 2 … 와 같이 가중치가 증가한다.

   1 -- 3    
   |  / |    
   | /  |    
   4 -- 2    
   |    
   5

• 1의 케빈 베이컨의 수: 6 (2+1+1+2)
• 2의 케빈 베이컨의 수: 8 (2+1+2+3)
• 3의 케빈 베이컨의 수: 5 (1+1+1+2)
• 4의 케빈 베이컨의 수: 5 (1+2+1+1)
• 5의 케빈 베이컨의 수: 8 (2+3+2+1)

노드마다 단계를 거쳐 구한 케빈 베이컨 수에 따라 최단 경로를 갖는 노드는 3과 4인 것을 확인할 수 있고,

출력 조건에 따라 번호가 가장 작은 3이 답이 될 수 있다.

 

그래프 시작 시 모든 노드 간의 거리를 무한대(INF)로 초기화한 후 자기 자신의 위치는 0으로 초기화하는 작업이 필요하다.

 

   0  INF INF INF INF    
   INF  0  INF INF INF    
   INF INF  0  INF INF    
   INF INF INF  0  INF    
   INF INF INF INF  0

다음으로 입력 정보를 바탕으로 그래프를 업데이트한다.

   0  INF INF INF INF    
   INF  0   1   1 INF    
   INF   1  0   1 INF    
   INF   1   1  0   1    
   INF INF INF   1  0

여기까지 진행했다면 노드 자신의 위치는 0, 쌍으로 연결된 노드 간의 위치는 1로 업데이트되고, 플로이드-와샬 알고리즘을 적용해
모든 노드 간의 최단 거리를 계산할 수 있다.

 

 

플로이드-와샬 알고리즘은 노드간의 중간 지점을 통해 항상 성립하는 관계가 있다는 걸 전제로 동작하고, 최단 경로를 찾기 위해 중간 노드를 이용한다.

중간점을 변경하면서 모든 노드 쌍에 대한 최단 경로를 업데이트하여 최종적으로 모든 노드 쌍 간의 최단 경로를 찾는 게 핵심인 것이다.

if 문

if (graph[i][j] > graph[i][k] + graph[k][j]) 이 부분이 참이 되는 경우는 다음을 의미한다.

• graph[i][j]: 노드 i에서 노드 j로 가는 현재까지 계산된 최단 경로의 거리를 나타낸다.

 

• graph[i][k] + graph[k][j]: 노드 i에서 노드 k로 가는 경로의 길이와 노드 k에서 노드 j로 가는 경로의 길이를 합친 값으로 이것은 노드 i에서 노드 j로 가는 경로 중에 노드 k를 거치는 경로의 길이를 나타낸다.

 

따라서 graph[i][j] > graph[i][k] + graph[k][j]가 참이라는 것은 현재까지 계산된 노드 'i’에서 'j’로 가는 최단 경로보다, 노드 'i’에서 'k’로 가는 경로와 ‘k’에서 'j’로 가는 경로를 합친 값이 더 작다는 것을 의미한다.

 

다시 말해 중간 경로를 통해 'j’로 가는 더 짧은 경로를 찾았다는 것을 나타내고, 그 값으로 업데이트한다.

    0  2  1  1  2 -> 6    
    2  0  1  2  3 -> 8    
    1  1  0  1  2 -> 5    
    1  2  1  0  1 -> 5    
    2  3  2  1  0 -> 8

마지막으로 각 행을 돌면서 가장 작은 켈빈 베이컨의 수를 찾고, 그에 맞는 번호를 반환하자.

---

풀이

[BufferedReader + Floyd-Warshall] 사용해 풀이한다.

package backjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class KevinBacon {
    static int N, M;
    static int INF = 1000000000;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");

        N = Integer.parseInt(temp[0]);
        M = Integer.parseInt(temp[1]);

        // 그래프 초기화
        graph = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }

        // 입력 정보로 그래프 업데이트
        for (int i = 0; i < M; i++) {
            temp = br.readLine().split(" ");
            int a = Integer.parseInt(temp[0]);
            int b = Integer.parseInt(temp[1]);
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        // 플로이드-와샬 알고리즘을 사용하여 모든 쌍 최단 경로 계산
        // k:중간점 i:시작점 j:끝점
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }

        int minBacon = INF;
        int result = 0;

        // 각 사용자(노드)에 대한 베이컨 수 계산
        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= N; j++) {
                sum += graph[i][j];
            }
            if (sum < minBacon) {
                minBacon = sum;
                result = i;
            }
        }
        System.out.println(result);
    }
}

그래프가 0부터 시작하면 헷갈릴 여지가 있기 때문에 주어진 크기(유저 수)에 1을 더했다는 것에 주의하자.

 

---