/ BOJ

BOJ_1389_케빈베이컨의6단계법칙_JAVA

문제 : 케빈 베이컨의 6단계 법칙

링크 : BOJ_1389_케빈베이컨의6단계법칙

접근 방식

케빈 베이컨의 6단계 법칙은 6사람만 거쳐가면 전 세계 그 누구와도 연결될 수 있다는 법칙이다.

이 문제는 그래프 문제인데, 특정 그래프 그룸에서 간선 정보가 주어지면, 간선을 바탕으로 한 사람 당 연결되어있는 사람 수를 구하는 것이 해결방안이다.

BFS로도 풀 수 있고, 플루이드 워샬을 이용하여 풀 수도 있다.

여기서는 플루이드 워샬을 이용하여 풀어보도록 하겠다.

소스 코드

import java.util.Scanner;

public class BOJ_1389_케빈베이컨의6단계법칙 {

	static final int INF = 9999999;
	static int N, adjMatrix[][], M;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		adjMatrix = new int[N+1][N+1];

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				adjMatrix[i][j] = INF;
				if(i==j) {
					adjMatrix[i][j] = 0;
				}
			}
		}

		for (int i = 0; i < M; ++i) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			adjMatrix[a][b] = 1;
			adjMatrix[b][a] = 1;
		}
		// 출발지-->경유지-->목적지로 3중 루프 돌리면 오답
		// 경유지-->출발지-->목적지로 3중 루프 돌려야 정답
		for (
				int k = 1; k <= N; ++k) {
			for (int i = 1; i <= N; ++i) {
				if (i == k)
					continue; // 출발지와 경유지가 같다면 다음 출발지
				for (int j = 1; j <= N; ++j) {
					if (i == j || k == j)
						continue; // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 패스
					if (adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
						adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
					}
				}
			}
		}
        int result = INF;
        int index = -1;

        // 케빈 베이컨의 수가 가장 작은 행을 탐색
        for (int i = 1; i <= N; i++) {
            int total = 0;
            for (int j = 1; j <= N; j++) {
                total += adjMatrix[i][j];
            }

            if (result > total) {
                result = total;
                index = i;
            }
        }

        System.out.println(index);

	}

}