[백준 / Java] 1389: 케빈 베이컨의 6단계 법칙 (BFS)

난이도: Silver 1

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

 

문제

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

---

 

양방향 그래프를 연결하면 된다.

BFS로 해결할 것이므로 그래프, 방문 체크 배열(visited)은 반드시 필요하고,

각 숫자별 단계 저장 배열(stage), 케빈 베이컨의 수 저장 배열(kevin)도 필요하다.

 

각 숫자별 단계 저장 배열은 bfs를 돌릴 때마다 새로 생성할 것이다. 

케빈 베이컨의 수 저장 배열은 단계 저장 배열을 모두 더한 값을 처음 bfs를 돌릴 때 시작한 숫자 인덱스에 저장한다.

예를 들면 bfs를 1부터 돌렸으면, kevin[1]에 stage[2] + stage[3] + stage[4] + stage[5]를 저장한다는 것이다.

 

 

*그래프를 만드는 방법

 

1. 그래프 (리스트 배열) 변수 선언

ArrayList<Integer>[] graph = new ArrayList[N + 1];   

 

2. 그래프 초기화

for (int i = 1; i <= N; i++) {

    graph[i] = new ArrayList<>();

}

 

3. 숫자들을 그래프에 연결

int A, B  // 입력받은 수

graph[A].add(B)

graph[B].add(A)

 

 

 

문제에 주어진 친구 관계대로 그래프를 연결하면 다음과 같다.

 

 

이제 1부터 5까지 각 지점마다 가는 데 몇 단계를 거쳐야 하는지 알아내면 된다.

 

 

bfs를 1부터 시작한다.             => start = 1

큐에 시작점(1)을 삽입하고      => queue.add(1)

시작점(1)을 방문 체크 해준다. => visited[1] = true

 

이제부터 반복문을 돌린다.

큐가 빌 떄까지 반복할 것이다.

 

큐에 있는 숫자를 하나 뺀다. => now = 1

int now = queue.poll();

1과 연결되어있는 숫자들을 모두 탐색한다. => graph[1] = { 3, 4 }

이 숫자(3, 4)들은 next로 들어갈 것이다.

for (int next : graph[now]) { 

    1과 연결되어있는 숫자들을 방문하지 않았다면 큐에 삽입하고 방문 체크를 한다.

    그리고 연결된 숫자의 단계는 현재 숫자의 단계 + 1을 해준다. => stage[3] = stage[1] + 1

    if (!visited[next]) {

        queue.add(next);

        visited[next] = true;

        stage[next] = stage[now] + 1;

    }

}

 

stage[next] = stage[now] + 1 (인접한 다음 지점의 단계 = 현재 지점의 단계 + 1)

 

1에서 3까지는 1단계를 거쳐야 하고  => stage[3] = stage[1] + 1 = 0 + 1 = 1

1에서 4까지는 1단계를 거쳐야 하고  => stage[4] = stage[1] + 1 = 0 + 1 = 1

1에서 2까지는 2단계를 거쳐야 하고  => stage[2] = stage[3] + 1 = 1 + 1 = 2

1에서 5까지는 2단계를 거쳐야 한다. => stage[5] = stage[4] + 1 = 1 + 1 = 2

 

그러므로 1의 케빈 베이컨의 수는 1 + 1 + 2 + 2 = 6이다.

=> kevin[1] = stage[2] + stage[3] + stage[4] + stage[5] = 6

 

 

stage[next] = stage[now] + 1 (인접한 다음 지점의 단계 = 현재 지점의 단계 + 1)

 

2에서 3까지는 1단계를 거쳐야 하고  => stage[3] = stage[2] + 1 = 0 + 1 = 1

2에서 1까지는 2단계를 거쳐야 하고  => stage[1] = stage[3] + 1 = 1 + 1 = 2

2에서 4까지는 2단계를 거쳐야 하고  => stage[4] = stage[3] + 1 = 1 + 1 = 2

2에서 5까지는 3단계를 거쳐야 한다. => stage[5] = stage[4] + 1 = 2 + 1 = 3

 

그러므로 2의 케빈 베이컨의 수는 1 + 2 + 2 + 3 = 8이다.

=> kevin[2] = stage[1] + stage[3] + stage[4] + stage[5] = 8

 

 

stage[next] = stage[now] + 1 (인접한 다음 지점의 단계 = 현재 지점의 단계 + 1)

 

3에서 1까지는 1단계를 거쳐야 하고  => stage[1] = stage[3] + 1 = 0 + 1 = 1 

3에서 2까지는 1단계를 거쳐야 하고  => stage[2] = stage[3] + 1 = 0 + 1 = 1

3에서 4까지는 1단계를 거쳐야 하고  => stage[4] = stage[3] + 1 = 0 + 1 = 1

3에서 5까지는 2단계를 거쳐야 한다. => stage[5] = stage[4] + 1 = 1 + 1 = 2 

 

그러므로 3의 케빈 베이컨의 수는 1 + 1 + 1 + 2 = 5이다.

=> kevin[3] = stage[1] + stage[2] + stage[4] + stage[5] = 5

 

 

stage[next] = stage[now] + 1 (인접한 다음 지점의 단계 = 현재 지점의 단계 + 1)

 

4에서 1까지는 1단계를 거쳐야 하고  => stage[1] = stage[4] + 1 = 0 + 1 = 1

4에서 5까지는 1단계를 거쳐야 한다. => stage[5] = stage[4] + 1 = 0 + 1 = 1

4에서 3까지는 1단계를 거쳐야 하고  => stage[3] = stage[4] + 1 = 0 + 1 = 1

4에서 2까지는 2단계를 거쳐야 하고  => stage[2] = stage[3] + 1 = 1 + 1 = 2

 

그러므로 4의 케빈 베이컨의 수는 1 + 1 + 1 + 2 = 5이다.

=> kevin[4] = stage[1] + stage[2] + stage[3] + stage[5] = 5

 

 

stage[next] = stage[now] + 1 (인접한 다음 지점의 단계 = 현재 지점의 단계 + 1)

 

5에서 4까지는 1단계를 거쳐야 한다. => stage[4] = stage[5] + 1 = 0 + 1 = 1

5에서 1까지는 2단계를 거쳐야 하고  => stage[1] = stage[4] + 1 = 1 + 1 = 2

5에서 3까지는 2단계를 거쳐야 하고  => stage[3] = stage[4] + 1 = 1 + 1 = 2

5에서 2까지는 3단계를 거쳐야 하고  => stage[2] = stage[3] + 1 = 2 + 1 = 3

 

그러므로 5의 케빈 베이컨의 수는 1 + 2 + 2 + 3 = 8이다.

=> kevin[5] = stage[1] + stage[2] + stage[3] + stage[4] = 8

 

 

kevin[1] = 6

kevin[2] = 8

kevin[3] = 5   // 최솟값

kevin[4] = 5   // 최솟값

kevin[5] = 8

 

이 중 배열 값이 가장 작은 값은 5이고, 이에 해당하는 인덱스는 3, 4이다.

즉, 케빈 베이컨의 수가 가장 작은 인덱스는 3, 4이다.

하지만 값이 여러개가 나오면 그 중 가장 작은 값을 출력하라고 했으니 최종 답은 3이 된다.

 

 

주석에도 설명을 한 줄 한 줄 자세히 적어 놓았다.

자, 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class P1389_케빈베이컨의6단계법칙 {
    static int N;                        // 유저의 수
    static ArrayList<Integer>[] graph;    // 그래프를 나타낼 리스트(1차원) 배열(1차원) => 2차원
    static int[] kevin;                    // 케빈 베이컨의 수를 저장하는 1차원 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());        
        int M = Integer.parseInt(st.nextToken());    // 친구 관계의 수
        graph = new ArrayList[N + 1];
        kevin = new int[N + 1];            
        
        // 1부터 N까지 모두 리스트 공간을 만들어주어야 함
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 친구 관계를 그래프에 연결하기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            graph[A].add(B);    // 양방향 연결
            graph[B].add(A);
        }
        
        // 1 ~ N까지 모두 bfs 수행
        for (int i = 1; i <= N; i++) {
            bfs(i);
        }
        
        int minIndex = 1;    // 케빈 베이컨의 수가 가장 작은 인덱스(사람)
        
        for (int i = 1; i <= N; i++) {
            // 케빈 배이컨의 수가 가장 작은 인덱스의 배열 값보다 지금 인덱스의 배열 값이 더 작다면
            if (kevin[i] < kevin[minIndex]) {
                minIndex = i;    // 케빈 베이컨의 수가 가장 작은 인덱스 갱신
            }
        }
        
        System.out.println(minIndex);    // 케빈 베이컨의 수가 가장 작은 인덱스(사람) 출력
    }
    
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();    // bfs 수행을 위한 큐
        boolean[] visited = new boolean[N + 1];        // 1차원 방문 체크 배열
        int[] stage = new int[N + 1];                // 1차원 단계 저장 배열
 
        queue.add(start);            // 큐에 시작 숫자 삽입
        visited[start] = true;        // 시작 숫자를 방문 체크
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int now = queue.poll();        // 큐에서 현재 숫자 뽑기
            
            // 현재 숫자와 연결된 숫자들 탐색
            for (int next : graph[now]) {
                if (!visited[next]) {        // 연결된 숫자를 방문하지 않았다면
                    queue.add(next);        // 큐에 연결된 숫자 삽입
                    visited[next] = true;    // 연결된 숫자를 방문 체크
                    stage[next] = stage[now] + 1;    // 연결된 숫자의 단계 = 현재 숫자의 단계 + 1
                }
            }
        }
        
        // 1부터 N까지 단계의 수를 모두 더해서 맨 처음 숫자의 케빈 베이컨의 수로 저장
        for (int i = 1; i <= N; i++) {
            kevin[start] += stage[i];
        }
    }
}