[알고리즘 PS] 백준 1389 케빈 베이컨의 6단계 법칙 자바 문제풀이

문제

해당 포스팅은 백준의 1389번 케빈 베이컨의 6단계 법칙 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

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

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 어느 한 노드에서 모드 노드 까지 방문하는데 걸리는 최소 비용을 물어보는 문제이다.

 

해결법

DFS 나 BFS 모두를 이용해서 풀 수 있지만 나는 BFS 를 이용해서 풀었다.

 

처음에는 방문 배열과 노드까지 걸리는 비용을 하나의 배열에서 관리했지만, 모든 방문 노드의 총 합을 구할 때 최초 노드를 방문 처리하기 위해 1을 더한 것이 문제를 일으켰기 때문에 방문 배열과 깊이 배열을 따로 나누어서 관리했다.

 

정답 코드

public class Main {

    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;
    private static int[] depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");

        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            String[] s = br.readLine().split(" ");
            int from = Integer.parseInt(s[0]);
            int to = Integer.parseInt(s[1]);

            graph.get(from).add(to);
            graph.get(to).add(from);
        }

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

        for(int i = 1; i <= n; i++) {
            depth = new int[n + 1];
            visited = new boolean[n + 1];
            int kevinBaconNumber = getKevinBaconNumber(i);
            if(min > kevinBaconNumber) {
                min = kevinBaconNumber;
                index = i;
            }
        }

        bw.write(String.valueOf(index));

        bw.flush();
        bw.close();
    }

    private static int getKevinBaconNumber(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        visited[start] = true;

        int sum = 0;

        while(!queue.isEmpty()) {
            int front = queue.remove();
            for(int value : graph.get(front)) {
                if(!visited[value]) {
                    visited[value] = true;
                    depth[value] = depth[front] + 1;
                    queue.add(value);
                }
            }
        }

        for (int i = 1; i < depth.length; i++) {
            sum += depth[i];
        }

        return sum;
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.