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

1.   💎 문제

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

• 케빈 베이컨의 수가 가장 작은 사람을 출력한다.
• 케빈 베이컨은 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다.

 

 

 

2. 🤔 어떻게 풀까?

사람마다 한명 씩 모든 사람과의 케빈 값을 구한 후 모두 더해, 가장 낮은 사람을 출력하면 되겠다.

케빈 값을 구하는 방법은 DFS를 사용해서 깊이를 더해주면서 구하면 되겠다.

 

하지만 틀렸다. DFS를 사용하면 모든 사람과의 관계의 단계를 알 수 있지만 단계의 최소는 알 수 없다. 즉 가장 최소의 사람을 찾을 수 없다.

생각의 전환이 필요하다.

 

최소 비용을 구할 수 있는 그래프 탐색은 BFS!

DFS로 구현할 수 있으면, 거의 BFS로도 구할 수 있으며, 경로를 알 수 있다는 장점이 있다. BFS로 탐색을 하면서 케빈 값(깊이)가 작은 걸로 갱신을 하며 구해보자!

 

BFS 탐색은 시작하는 노드를 기준으로 다른 노드를 처음 방문했을 때가 최소임을 보장된다. 그러므로 방문을 하기만 하면 언제나 그 값을 갈 수 있는 최단 경로이므로 `isVisited` 변수를 사용하여 방문 여부를 체크하며 탐색을 진행한다.

  public static void getKevinValues(int start){
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(start, 0));

        while(!que.isEmpty()){
            Node curNode = que.poll();
            kevinValues[start][curNode.x] = curNode.depth;

            for(int friend : friends[curNode.x]){
                if(!isVisited[friend]){
                    que.add(new Node(friend, curNode.depth +1));
                    isVisited[friend] = true;
                }
            }
        }
    }

 

이러한 방식으로 루프를 돌며 1번째 요소부터 N번째 요소의 케빈 값들을 모두 구한다. 한 요소의 케빈 값들을 모두 구할 때마다 `isVisited`를 초기화하며, 케빈 값을 모두 더하여, 최소의 케빈 값을 갖는 요소인지 판단한다. 최소가 되는 사람 `ans`를 결과로 출력한다.

 // 차례대로 케빈 값을 구함
        for(int i=1; i<=N; i++){
            int sum = 0;
            isVisited = new boolean[N+1];
            isVisited[i] = true;
            getKevinValues(i);

            // 총 케빈 베이컨의 합
            for(int kevin : kevinValues[i])
                sum += kevin;

            // 작을 때 갱신
            if(kevinMin > sum){
                ans = i;
                kevinMin = sum;
            }

        }

 

 

3. 📄 전체 코드

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

public class Main {

    static ArrayList<Integer> [] friends;
    static int N;
    static int M;
    static int [][] kevinValues;
    static boolean [] isVisited;
    static int ans;
    static long kevinMin;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 유저의 수
        N = Integer.parseInt(st.nextToken());
        // 친구 관계의 수
        M = Integer.parseInt(st.nextToken());

        friends = new ArrayList[N+1];
        kevinValues = new int[N+1][N+1];

        for(int i=1; i<=N; i++)
            friends[i] = new ArrayList<>();

        // 친구 관계 입력
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            friends[start].add(end);
            friends[end].add(start);
        }

        // 케빈 값들 초기화
        for(int row=0; row< kevinValues.length; row++){
            for(int col=0; col<kevinValues[0].length; col++){
                kevinValues[row][col] = Integer.MAX_VALUE;
            }
        }
        kevinMin = Long.MAX_VALUE;

        // 차례대로 케빈 값을 구함
        for(int i=1; i<=N; i++){
            int sum = 0;
            isVisited = new boolean[N+1];
            isVisited[i] = true;
            getKevinValues(i);

            // 총 케빈 베이컨의 합
            for(int kevin : kevinValues[i])
                sum += kevin;

            // 작을 때 갱신
            if(kevinMin > sum){
                ans = i;
                kevinMin = sum;
            }

        }
        bw.write(Integer.toString(ans));
        bw.flush();

        bw.close();
        br.close();
    }
    public static void getKevinValues(int start){
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(start, 0));

        while(!que.isEmpty()){
            Node curNode = que.poll();
            kevinValues[start][curNode.x] = curNode.depth;

            for(int friend : friends[curNode.x]){
                if(!isVisited[friend]){
                    que.add(new Node(friend, curNode.depth +1));
                    isVisited[friend] = true;
                }
            }
        }
    }
}

class Node{
    int x;
    int depth;

    Node(int x, int depth){
        this.x = x;
        this.depth = depth;
    }
}