백준 1389번 : 케빈 베이컨 6단계 법칙 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

케빈 베이컨 6단계 법칙 실버 1

 

📖 문제

 

어디서 많이 봤던 문제

촌수 따지는 문제랑도 비슷한 것 같다.

 

다른점은 모든 사람들의 케빈 베이컨 지수 중 가장 작은 지수를 가진 사람을 찾는 것

즉, 모든 사람에 대한 모든 사람의 최단거리, 플로이드 와샬 알고리즘을 쓸 수 있다.

 

BFS로 그냥 풀어도 된다.

 

 

---

🔅 문제 풀이 (플로이드 와샬)

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

public class Main {

    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());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n + 1][n + 1];
        
        // 무한으로 설정
        for (int i = 1; i <= n; i++) {
            Arrays.fill(arr[i], 1000000);
        }

        // 자기자신은 거리 0
        for (int i = 1; i <= n; i++) {
            arr[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            arr[A][B] = arr[B][A] = 1;
        }

        // a -> b , a->k-b  중 최단거리 구하기 
        for (int k = 1; k <= n; k++) {
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    arr[a][b] = Math.min(arr[a][b], arr[a][k] + arr[k][b]);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        int answer = 0;

        for (int i = 1; i <= n; i++) {
            int sum = Arrays.stream(arr[i]).sum(); // 베이컨 지수 합을 구하기

            if (min > sum) { // 가장 적은 지수를 가진 사람 갱신
                min = sum;
                answer = i;
            }
        }

        bw.write(answer + "");
        bw.flush();
        bw.close();

    }


}

 

 

🔅 문제 풀이 (BFS)

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

public class Main {

    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());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] arr = new boolean[n + 1][n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

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

        int min = Integer.MAX_VALUE;
        int answer = 0;

        for (int i = 1; i <= n; i++) {
            boolean[] visited = new boolean[n + 1];
            int degree = bfs(arr, visited, i);

            // 케빈 베이컨 지수 최솟값 갱신
            if (min > degree) { // 같을때는 갱신하지 않으므로 번호가 가장 낮은 사람을 보장
                min = degree;
                answer = i; 
            }
        }

        bw.write(answer + "");
        bw.flush();
        bw.close();

    }

    private static int bfs(boolean[][] graph, boolean[] visited, int start) {
        Queue<int[]> q = new LinkedList<>();
        visited[start] = true;
        q.add(new int[] {start, 1});

        int sum = 0;

        while (!q.isEmpty()) {
            int[] node =  q.poll();

            for (int i = 1; i < graph.length; i++) {
                if (graph[node[0]][i] && !visited[i]) {
                    visited[i] = true;
                    sum += node[1];

                    q.add(new int[]{i, node[1] + 1});
                }
            }

        }

        return sum;
    }

}

❗ 오답노트 / 필요한 지식

1.