Graph : 백준 케빈 베이컨의 6단계 법칙 - 1389

문제 유형

Grpah - BFS

작성 코드

import java.util.*;

public class Main {
    static int N, M;
    static Map<Integer, List<Integer>> nodeMap;
    static int[] visited;

    public static void input() {
        Scanner sc = new Scanner(System.in);
        // # of nodes
        N = sc.nextInt();
        // # of relationship
        M = sc.nextInt();

        nodeMap = new HashMap<>();

        for (int i = 1; i < N + 1; i++) {
            nodeMap.put(i, new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            nodeMap.get(from).add(to);
            nodeMap.get(to).add(from);
        }
    }

    public static void pro() {
        int currentMin = Integer.MAX_VALUE;
        int currentMinIndex = -1;
        for (int i = 1; i < N + 1; i++) {
            int temp = bfs(i);
            if (temp < currentMin) {
                currentMin = temp;
                currentMinIndex = i;
            }
        }
        System.out.println(currentMinIndex);
    }

    public static int bfs(int from) {
        Deque<Integer> bfsQueue = new LinkedList<>();
        bfsQueue.add(from);
        visited = new int[N + 1];
        Arrays.fill(visited, -1);
        visited[from] = 0;
        while (!bfsQueue.isEmpty()) {
            int node = bfsQueue.pollFirst();
            List<Integer> toNodes = nodeMap.get(node);

            for (int to : toNodes) {
                if (visited[to] == -1) {
                    visited[to] = visited[node] + 1;
                    bfsQueue.add(to);
                }
            }

        }
        int temp = 0;
        for (int i = 1; i < visited.length; i++) {
            temp+= visited[i];
        }
        return temp;
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

접근방식

1. 시작 Node에서 다른 Node로의 방문을 다 확인해야하고
2. 다른 Node에 몇번에 걸쳐서 가야하는지를 알아야 하기 때문에  bfs를 사용했다.