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

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

---

문제 설명

문제 설명이 길고 복잡한데 플로이드 와샬 알고리즘을 적용하면 쉬게 풀리는 문제입니다.

2차원 배열 distance를 만들어 자기 자신이외는 전부 INF(무한대)로 초기화 합니다. 다음 입력받는 연결에 대하여 양방향으로 A-B, B-A를 1로 저장 합니다. 아래의 3차원 for문을 사용하여 각각의 단계로 가는 최소값을 갱신합니다. 마지막으로 그중 가장 작은 합이 정답이 됩니다.

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] distance = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(distance[i], 5001);
            distance[i][i] = 0;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            distance[A][B] = distance[B][A] = 1;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }

        int answer = -1;
        int min = Integer.MAX_VALUE;

        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= N; j++) {
                sum += distance[i][j];
            }

            if (min > sum) {
                answer = i;
                min = sum;
            }
        }

        System.out.println(answer);
    }
}