BOJ - 케빈 베이컨의 6단계 법칙

 

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

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

 

• 주어진 사람과 관계 수를 인접 리스트로 만든 뒤 사람 순서대로 너비우선탐색을 했음.
• 사람 관계에서 가중치가 없는 노드이기 때문에 depth를 케빈 베이컨 수로 사용
• 1번째 사람부터 N번쨰 사람까지 BFS 결과를 리턴

 

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


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 유저 수
        int N = Integer.parseInt(st.nextToken());

        // 관계 수
        int M = Integer.parseInt(st.nextToken());

        //인접 행렬
        ArrayList<Integer>[] adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        //간선
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dst = Integer.parseInt(st.nextToken());
            adj[src].add(dst);
            adj[dst].add(src);
        }

        int minPath = Integer.MAX_VALUE;
        int minId = 0;
        for (int i = 1; i <= N; i++) {
            int path = bfs(i, adj, N);
            if(minPath > path) {
                minId = i;
                minPath = path;
            }
        }
        System.out.println(minId);
    }

    private static int bfs(int start, ArrayList<Integer>[] adj, int n) {
        boolean[] visited = new boolean[n + 1];

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(start, 0));

        int sumOfPath = 0;
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (visited[current.index]) continue;
            visited[current.index] = true;

            sumOfPath += current.depth;

            for (int i = 0; i < adj[current.index].size(); i++) {
                Integer next = adj[current.index].get(i);
                if (visited[next]) continue;
                queue.offer(new Node(next, current.depth + 1));
            }
        }

        return sumOfPath;
    }

    static public class Node {
        public int index;
        public int depth;

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