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

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

728x90

문제

해당 포스팅은 백준의 1389번 케빈 베이컨의 6단계 법칙 의 접근과 해결 방법을 설명한 글 입니다.

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

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

문제 접근

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

해결법

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

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

정답 코드

public class Main { private static List> 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 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 에서 확인 가능합니다.

728x90

from http://wonit.tistory.com/564 by ccl(S) rewrite - 2021-08-03 02:00:25