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

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

[백준 1389]

문제 분석하기

BFS 탐색 알고리즘을 이용해도 해결할 수 있는 문제이지만, 유저의 최대 수가 100 정도로 작기 때문에 플로이드-워셜 알고리즘 이용

1번째로 사람들이 직접적인 친구 관계를 맺은 상태를 비용 1로 계산하여 인접 행렬에 저장하는 방법으로 접근

손으로 풀어보기

1. 친구 관계 정보를 인접 행렬에 저장
   • 자기 자신이면 0, 아니면 충분히 큰 수로 인접 행렬의 값을 초기화
   • 그리고 주어진 친구 관계 정보를 인접 행렬에 저장
2. 플로이드-워셜 알고리즘을 수행
3. 케빈 베이컨의 수를 비교해 가장 작은 수가 나온 행 번호를 정답으로 출력

슈도코드 작성하기

N(유저 수) M(친구 관계 수)
distance(친구 관계 데이터를 저장하는 인접 행렬)
for(i -> N만큼 반복하기) {
    for(j -> N만큼 반복하기) {
        시작 친구와 종료 친구가 같으면(자기 자신이면) 0, 아니면 충분히 큰 수로 저장하기
    }
}
for(M만큼 반복하기) {
    친구 관계 데이터를 distance 행렬에 저장하기
    친구 관계는 서로 관계를 맺는 것이므로 양방향 엣지로 저장하고 가중치를 1로 함
}
for(k -> N만큼 반복하기) {
    for(i -> N만큼 반복하기) {
        for(j -> N만큼 반복하기) {
            i ~ j 사이에 가능한 모든 경로를 탐색하기
            distance[i][j]에 distance[i][k] + distance[k][j] 값들 중 최솟값 넣기
        }
    }
}
MIN(충분히 큰 수로 초기화) {
for(i -> N만큼 반복하기) {
    for(j -> N만큼 반복하기) {
        각 배열의 값을 합치기 -> i의 케빈 베이컨의 수
    }
    if(MIN > i의 케빈 베이컨의 수)
        MIN값을 i의 케빈 베이컨의 수로 저장하기
}
가장 작은 케빈 베이컨의 수를 지니고 있는 i 출력하기

코드 구현하기

/**
 * 1389) 케빈_베이컨의_6단계_법칙
 */
public class D063_1389 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N(유저 수)
        int N = Integer.parseInt(st.nextToken());
        // M(친구 관계 수)
        int M = Integer.parseInt(st.nextToken());
        // distance(친구 관계 데이터를 저장하는 인접 행렬)
        int distance[][] = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // 시작 친구와 종료 친구가 같으면(자기 자신이면) 0
                if (i == j)
                    distance[i][j] = 0;
                // 아니면 충분히 큰 수로 저장하기
                else
                    distance[i][j] = 10000001;
            }
        }
        // 친구 관계 데이터를 distance 행렬에 저장하기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            // 친구 관계는 서로 관계를 맺는 것이므로 양방향 엣지로 저장하고 가중치를 1로 함
            distance[s][e] = 1;
            distance[e][s] = 1;
        }
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // distance([i][j])에 distance[i][k] + distance[k][j] 값들 중 최솟값 넣기
                    // Math.min(D[I][J], D[I][K] + D[K][J])
                    if (distance[i][j] > distance[i][k] + distance[k][j])
                        distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }
        // MIN(충분히 큰 수로 초기화)
        int Min = Integer.MAX_VALUE;
        int Answer = -1;
        // 각 배열의 값을 합치기 (i의 케빈 베이컨의 수)
        for (int i = 1; i <= N; i++) {
            int temp = 0;
            for (int j = 1; j <= N; j++) {
                temp = temp + distance[i][j];
            }
            if (Min > temp) {
                // MIN값을 i의 케빈 베이컨의 수로 저장하기
                Min = temp;
                Answer = i;
            }
        }
        // 가장 작은 케빈 베이컨의 수를 지니고 있는 i 출력하기
        System.out.println(Answer);
    }
}