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

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

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

[풀이 방법]

이 문제 역시 dfs, bfs, 플로이드 와샬 알고리즘 등 다양한 방법으로 풀 수 있다.

난 플로이드 와샬 알고리즘으로 풀어봐야지... 가장 간단한 방법인 것 같다.

   1. 첫째 줄에 N과 K를 입력받는다. N은 정점, K는 간선의 수라고 생각했다.

   2. relation이라는 N+1 X N+1 행렬을 생성 후 이후에 나오는 간선 정보들을 저장했다.

      여기서, 1이 3을 알때 3도 1을 안다고 볼 수 있으므로

               relation[1][3] = 1

               relation[3][1] = 1

      을 해준다.

   3. 탐색을 시작한다.

relation[r][k] != 0이고 relation[k][c] != 0 일때

               -relation[r][c] == 0이면 

        relation[r][c] = relation[r][k] + relation[k][c]

               -relation[r][c] != 0이면 

  relation[r][c] = relation[r][c] < relation[r][k]+relation[k][c] ? relation[r][c]  relation[r][k]+relation[k][c]

   4. 탐색이 끝나면 케빈베이컨수가 가장 작은 사람을 출력해 주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        int[][] relation = new int[N + 1][N + 1];
        int r, c;
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            relation[r][c] = 1;
            relation[c][r] = 1;
        }
 
        for (int k = 1; k <= N; k++) {
            for (int row = 1; row <= N; row++) {
                for (int col = 1; col <= N; col++) {
                    if (relation[row][k] != 0 && relation[k][col] != 0 && row != col) {
                        if (relation[row][col] == 0) {
                            relation[row][col] = relation[row][k] + relation[k][col];
                        } else {
                            relation[row][col] = Math.min(relation[row][col], relation[row][k] + relation[k][col]);
                        }
 
                    }
                }
            }
        }
 
        int min = Integer.MAX_VALUE;
        int sum = 0;
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                sum += relation[i][j];
            }
            if (min > sum) {
                min = sum;
                ans = i;
            }
            sum = 0;
        }
        System.out.println(ans);
    }
}