P1389. 케빈 베이컨의 6단계 법칙

- 문제: https://www.acmicpc.net/problem/1389

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

설명

 

1. 

모든 정점사이의 최단거리를 구한다.

2차원 배열의 모든 값을 INF로 초기화하고, (1,1), (2,2), ... (i,i)인 값을 0으로 초기화한다.

 

2.

간선은 양방향으로 초기화한다.

arr[1][3] = arr[3][1] = 1

 

3.

플로이드 와샬 알고리즘을 실행하여, 최단 경로를 찾는다.

arr[i][j] > arr[i][k] + arr[k][j] 이면, arr[i][j] = arr[j][k] + arr[k][j]로 초기화한다.

+) 플로이드 와샬 알고리즘

- 주어진 그래프의 간선의 연결 상태를 고려한다. 

- 노드에서 노드로 가는 간선이 여러 개인 경우, 간선 중 최소 비용을 구한다.

- 간선의 개수를 0개, 1개, ... , N개로 늘려가면서 최소 거리 비용을 업데이트한다.

 

4. 

케빈 베이컨의 최소 개수에 해당하는 인덱스를 탐색한다.

 

코드

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

public class Main {
    static final int INF = 987654321;
    static int N, M;
    static int[][] person;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());   // 유저의 수
        M = Integer.parseInt(st.nextToken());   // 친구 관계의 수

        person = new int[N][N];

        // 초기값 설정
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                person[i][j] = INF;
                if (i == j) {
                    person[i][j] = 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());
            person[a - 1][b - 1] = 1;
            person[b - 1][a - 1] = 1;
        }

        // 플로이드 워샬 알고리즘 적용
        for (int k = 0; k < N; k++) {           // 거쳐가는 노드
            for (int i = 0; i < N; i++) {       // 출발 노드
                for (int j = 0; j < N; j++) {   // 도착 노드
                    person[i][j] = Math.min(person[i][j], person[i][k] + person[k][j]);
                }
            }
        }

        int result = Integer.MAX_VALUE;
        int r_index = 0;
        for (int i = 0; i < N; i++) {
            int total = 0;
            for (int j = 0; j < N; j++) {
                total += person[i][j];
            }
            if (result > total) {
                result = total;
                r_index = i;
            }
        }
        System.out.println(r_index + 1);
    }
}

 

Reference

https://steady-coding.tistory.com/95

https://sskl660.tistory.com/61

[Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)