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

문제 요약

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

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

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

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• 최단 경로
• 플로이드–워셜

문제 풀이

문제 자체는 쉽지만, 자바를 이용해서 제대로 푼 첫 문제가 되는 것 같다.
플로이드 워셜 알고리즘을 사용해서 최단 경로를 구했고, 그 안에서 케빈 베이컨 수를 구해서 가장 작은 번호를 출력했다.

BufferReader, BufferWriter, StringTokenizer를 처음 사용해봤는데, 항상 C++로만 개발을 해서 그런지 조금 낯설었다. 확실히 문법이 조금 어색한 느낌

앞으로 자바로 문제를 계속해서 풀다보면 익숙해질 것이다.

풀이 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static final int INF = 987654321;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] ary = new int[n + 1][n + 1];
        for(int i = 0; i <=n; i++) {
            for(int j = 0; j<= n; j++) {
                ary[i][j] = INF;
                if(i == j) ary[i][j] = 0;
            }
        }
        for(int i = 0; i < m ; i++) {
            st = new StringTokenizer(br.readLine());
            int in1 = Integer.parseInt(st.nextToken());
            int in2 = Integer.parseInt(st.nextToken());

            ary[in1][in2] = 1;
            ary[in2][in1] = 1;
        }

        for(int k = 1; k <= n; k++) {
            for(int i = 1;i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(ary[i][j] > ary[i][k] + ary[k][j])
                        ary[i][j] = ary[i][k] + ary[k][j];
                }
            }
        }
        int max = INF, sum;
        int maxi = 0;
        for(int i = 1; i <=n; i++) {
            sum = 0;
            for(int j = 1; j <= n; j++) {
                sum += ary[i][j];
            }
            if(max > sum) {
                max = sum;
                maxi = i;
            }
        }
        bw.write(Integer.toString(maxi));
        bw.flush();
        bw.close();
        br.close();
    }
}