[알고리즘][플로이드와샬][1389] 케빈 베이컨의 6단계 법칙

[알고리즘][플로이드와샬][1389] 케빈 베이컨의 6단계 법칙

* 문제

 https://www.acmicpc.net/problem/1389

 과거에 '링크'라는 책에서 이 법칙을 본 적이 있는데 알고리즘으로 풀면서 고생하니 더욱 인상깊은 법칙.....

 아무튼 풀이는 이렇다!

 초반에는 별 생각없이 DFS로 풀려고 덤볐다가 뭔가 잘못됐다는 것을 깨닳고 다시 풀기 시작했다. 

 이러한 문제에 가장 보편적으로 적용되는 알고리즘이 플로이드 와샬 알고리즘이라는 것을 처음 알게 되어 이에 대해 공부하고 다시 풀었다.

 알고리즘 자체도 이해가 쉽지 않았지만 몇몇 분들이 친절하게 설명을 해주셔서 보다 쉽게 이해했다.

 

* 풀이

 플로이드 와샬 알고리즘을 적용하여 푼다. 해당 알고리즘에 관한 설명은 http://heekim0719.tistory.com/ 를 참고해주세요.

 모든 경로를 짚어서 최단 경로를 찾아 배열에 넣어준다.

* 코드

package algorithm_DFS;
 
import java.util.Scanner;
 
public class q_1389 {
 
    static int[][] relation;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        relation = new int[n+1][n+1];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(i==j) relation[i][j] = 0;
                else relation[i][j] = 99;
            }
        }
        for(int i=0;i<m;i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            relation[x][y] = 1;
            relation[y][x] = 1;
        }
        for(int k=1;k<=n;k++) {
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=n;j++) {
                    if(relation[i][j] > relation[i][k]+relation[k][j]) {
                        relation[i][j] = relation[i][k]+relation[k][j];
                    }
                }
            }
        }
        
        int min = 99;
        int ans = 0;
        for(int i=1;i<=n;i++) {
            int sum =0;
            for(int j=1;j<=n;j++) {
                if(relation[i][j]!=99)
                    sum+=relation[i][j];
            }
            if(sum<min) {
                min = sum;
                ans = i;
            }
        }
        System.out.println(ans);
    }
 
}