Baekjoon #1389 케빈 베이컨의 법칙 (java)

접근 방법

처음에는 플로이드-워셜 알고리즘으로 풀어야겠다고 생각했었다. 모든 지점에서 다른 모든 지점까지의 최단경로를 구해야한다고 생각했기 때문이다.

하지만 알고리즘 분류가 BFS라서 다이나믹 프로그래밍을 사용하는 플로이드 워셜은 좋은 방법이 아닐 것 같다는 직감이 들었다. 일단 플로이드 워셜 알고리즘은 시간복잡도가 O(N^3)이기 때문에 별로 쓰고 싶지 않았다. (N이 최대 100이기 때문에 가능할 것 같기는 하다.)

 

좀 더 고민해보니 각 친구사이의 거리는 항상 1이므로 BFS 탐색으로 각 지점간의 최단거리를 보장할 수 있다는 것을 깨달았다. BFS는 시간복잡도 O(N)으로 이 경우에는 훨씬 효율적일 것이라고 생각했다. (단 모든 사람들을 모두 탐색해야하므로 O(N^2)이다.)

 

1. BFS로 각 사람 간 최단거리 탐색 → 사람 별 케빈베이컨 수 누계
2. 케빈베이컨 최소인 사람 구하기

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int N, M;
    static List<Integer>[] list;
    static int[] kbNum;
    static int min_value = 100;
    static int idx = 0;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) list[i] = new ArrayList<>();
        kbNum = new int[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());
            list[a].add(b);
            list[b].add(a);
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                kbNum[i] += networking(i, j);
            }
            //System.out.println("kbNum[" + i + "] " + kbNum[i]);
        }

        for (int i = 1; i < N + 1; i++) {
            if (kbNum[i] < min_value) {
                min_value = kbNum[i];
                idx = i;
            }
        }
        System.out.println(idx);
    }

    private static int networking(int start, int end) {
        int[] visited = new int[N + 1];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(start);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            if (v == end) {
                //System.out.println("start  = " + start + " end = " + end + " depth = " + visited[v]);
                return visited[v];
            }
            for (int u : list[v]) {
                if (visited[u] == 0) {
                    queue.offer(u);
                    visited[u] = visited[v] + 1;
                }
            }
        }
        return 0;
    }

}

출처

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

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