[JAVA] 백준 1389번_케빈 베이컨의 6단계 법칙

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

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

---

import java.util.*;

public class Main {
    static int N, M, n1, n2;
    static int[][] kbNum;
    static ArrayList<Integer>[] edges;
    static boolean[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        edges = new ArrayList[N + 1];
        kbNum = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            edges[i] = new ArrayList<Integer>();
        }
        while (M-- > 0) {
            n1 = sc.nextInt(); n2 = sc.nextInt();
            edges[n1].add(n2);
            edges[n2].add(n1);
        }
        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            bfs(i);
        }
        int kbMin = Integer.MAX_VALUE;
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            int tmp = Arrays.stream(kbNum[i]).sum();
            if(kbMin > tmp){
                answer = i;
                kbMin = tmp;
            }
        }
        System.out.println(answer);
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int i = 0; i < edges[now].size(); i++) {
                int next = edges[now].get(i);
                if(!visited[next]){
                    queue.add(next);
                    kbNum[start][next] = kbNum[start][now] + 1;
                    visited[next] = true;
                }
            }
        }
    }

}

 

💡 그래프, bfs 사용

int[][] kbNum = new int[N + 1][N + 1];

 : 1번째 ~ N번째 노드에서 출발하는 bfs 실시 → 각 노드를 출발점으로 했을 때 최단 경로를 배열에 기록함

  → 추후 1 ~ N까지 배열합(= 케빈 베이컨 수)을 구해서 최소 인덱스(=답) 출력

- 탐색에는 bfs 탐색 사용 (어느 노드에서 시작하는지 start값을 알아야 kbNum에 기록하기 때문에)

- 그래프는 ArrayList의 배열을 사용해 구현