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

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

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

---

케빈 베이커의 6단계 법칙!! 대충 모든 사람은 6다리 정도 거치면 서로가 서로를 아는 사람으로 이어질 수 있다는 법칙인데

아무래도 나같은 아싸를 계산에 넣지 않고 만든 법칙인듯하다ㅋㅋ

 

여튼 이 문제는 플로이드 와샬을 사용해서 풀면 된다. 어제 풀었던 플로이드 문제보다 훨씬 쉬운 문제이다. BFS 로도 풀이가 가능하다고 들었으나, 나는 플로이드 와샬 알고리즘을 공부하기 위해 이쪽으로 풀이를 해보았다.

 

풀이의 요점은 아래와 같다!

1. 3중 for 문을 사용해서 바로 가는 경우와 경유지를 들리는 경우 중 더 작은 값을 찾아서 저장한다.
2. 모든 배열은 INF(가장 큰 값 -> 987654321)으로 초기화하며, 자기 자신은 0으로 초기화!!
3. 베이컨의 수가 가장 작은 값이 아닌 '사람'을 구하는 것이 문제이다. 때문에 배열의 값이 아닌 배열의 index를 구해야한다. 나는 이를 위해서 ArrayList 를 하나 만들었고, comparator 를 사용해서 오름차순으로 정리해준 후 ArrayList 의 0번째 값을 구해서 답을 도출하였다.

 

나머지는 주석 참고!!

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/1389
// 플로이드 와샬 알고리즘 풀이 문제
// 3중 for 문 사용, 갈 수 없는 곳은 INF 로 초기화, 자기자신은 0으로 초기화 하는 것을 잊지말자!
public class Quiz_1389 {
    static final int INF = 987654321;
    static int[][] friend;
    static ArrayList<Member> member = new ArrayList<>();


    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        friend = new int[n+1][n+1];


        makeGraph(n, m);
        floydWarshall(n);
    }

    // 입력받은 정보로 그래프 생성
    static void makeGraph(int n, int m) throws IOException {
        StringTokenizer st;

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if (i == j) {
                    friend[i][j] = 0;
                }else{
                    friend[i][j] = INF;
                }
            }
        }

        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            friend[a][b] = 1;
            friend[b][a] = 1;
        }

    }

    // 플로이드 와샬 알고리즘 수행
    static void floydWarshall(int n){
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    friend[i][j] = Math.min(friend[i][j], friend[i][k] + friend[k][j]);
                }
            }
        }

        // sum 은 friend 의 합계
        // 즉 i 번째 사람의 케빈 베이컨 수의 합계
        for(int i=1; i<=n; i++){
            int sum = 0;
            for(int j=1; j<=n; j++){
                 sum += friend[i][j];
            }
            member.add(new Member(i, sum));
        }

        // sum 이 다른 경우 오름차순 정렬
        // sum 이 같은 겨우 index 오름차순 정렬
        member.sort(new Comparator<Member>() {
            @Override
            public int compare(Member o1, Member o2) {
                if (o1.sum != o2.sum) {
                    return o1.sum - o2.sum;
                } else {
                    return o1.index - o2.index;
                }
            }
        });

        // 전체가 오름차순으로 정렬되어있음으로
        // 배열에서 0번째 값을 꺼내서 index 를 출력
        System.out.println(member.get(0).index);

    }
}

class Member{
    int sum;
    int index;

    Member(int index, int sum) {
        this.sum = sum;
        this.index = index;
    }
}