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

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

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

문제 설명

케빈 베이컨의 수가 가장 작은 사람을 구하면 된다.

케빈 베이컨은 다른 사람을 알기 위해 걸치는 다리 수를 말한다. 예를 들면 다음과 같다.

A, B, C, D, E가 있고 A와 C, A와 D, B와 C, C와 D, D와 E가 친구인 경우를 생각해보자.

친구 관계도

발그림 죄송합니다

A의 케빈 베이컨을 구하면 다음과 같다.

• B를 알기 위해 C를 거쳐야 하므로 B와의 케빈 베이컨은 2이다.
• C는 이미 알고 있으므로 C와의 케빈 베이컨은 1이다.
• D와도 이미 알고 있으므로 D와의 케빈 베이컨은 1이다.
• E와는 D를 거쳐야 하므로 E와의 케빈 베이컨은 2이다.

따라서 A의 케빈 베이컨 총합은 2 + 1 + 1 + 2 = 6이 된다.

 

B의 케빈 베이컨을 구하면 다음과 같다.

• A를 알기 위해 C를 거쳐야 하므로 A와의 케빈 베이컨은 2이다.
• C는 이미 알고 있으므로 C와의 케빈 베이컨은 1이다.
• D를 알기 위해 C를 거쳐야 하므로 D와의 케빈 베이컨은 2이다.
• E를 알기 위해 C와 D를 거쳐야 하므로 E와의 케빈 베이컨은 3이다.

따라서 B의 케빈 베이컨 총합은 2 + 1 + 2 + 3 = 8이 된다.

 

이런 식으로 A부터 E까지 모든 사람의 케빈 베이컨을 구한 다음 가장 작은 케빈 베이컨인 사람을 구하면 된다. 만약 케빈 베이컨이 같다면 번호가 작은 사람을 출력한다.

풀이 방법

BFS를 활용해서 해결했다.

import java.io.*;
import java.util.*;

class Main {

    static int N, M;
    static boolean[][] network;
    static boolean[] isVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        network = new boolean[N + 1][N + 1];
        isVisited = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            split = br.readLine().split(" ");
            int A = Integer.parseInt(split[0]);
            int B = Integer.parseInt(split[1]);

            network[A][B] = true;
            network[B][A] = true;
        }

        Relation result = bfs();
        System.out.print(result.me);
    }

    private static Relation bfs() {
        Queue<Relation> q = new LinkedList<>();
        Relation min = new Relation(0, 0, Integer.MAX_VALUE);

        // 1부터 N까지 모든 사람의 케빈 베이컨을 구한다.
        for (int me = 1; me <= N; me++) {
            q.offer(new Relation(me, 1, 0));
            isVisited[me] = true;
            int kevinBacon = 0;

            while (!q.isEmpty()) {
                Relation r = q.poll();
                kevinBacon += r.cnt;

                // 현재 사람과 연결되어 있는 사람을 모두 찾는다.
                for (int you = 1; you <= N; you++) {
                    // 아직 만나지 않았고, 연결되어 있다면 카운트를 증가시키고 큐에 넣는다.
                    if (!isVisited[you] && network[r.me][you] == true) {
                        isVisited[you] = true;
                        q.offer(new Relation(you, 1, r.cnt + 1));
                    }
                }
            }

            // 케빈 베이컨이 작은 사람을 구한다.
            if (min.cnt > kevinBacon) {
                min = new Relation(me, 0, kevinBacon);
            // 같은 경우
            } else if (min.cnt == kevinBacon) {
                // 번호가 작은 사람으로 정한다.
                if (min.me > me)
                    min = new Relation(me, 0, kevinBacon);
            }

            // 다음 사람의 케빈 베이컨을 구하기 위해 초기화
            isVisited = new boolean[N + 1];
        }

        return min;
    }

    static class Relation {
        int me;
        int you;
        int cnt;

        public Relation(int me, int you, int cnt) {
            this.me = me;
            this.you = you;
            this.cnt = cnt;
        }
    }
}