[백준 - Java] 1389번 : 케빈 베이컨의 6단계 법칙

문제

www.acmicpc.net/problem/1389

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

풀이 전 여담 

풀고 나니 별거 아닌 문제였는데 많은 시간을 소비했다ㅠㅠ

일단 나는 BFS로 풀었다.

근데 검색해보니 이게 플로이드 와샬 알고리즘이라고 한다. (추후에 공부 다시 해서 정리할 것!!)

 

* BFS 원래 알고리즘 대로 쓰면 안 됨 조건이 필요

예제에서 1번과 5번 친구의 경우 (1, 3, 4, 5)로 4번 만에 친구가 되는데 (1, 4, 5)로 최소로 친구가 되어야 한다.

근데 그냥 BFS 탐색하면서 5번 찾았을때 BFS 끝내면 (1, 3, 4, 5)로 4를 리턴함 

BFS탐색하면서 최소로 가는 경우 구해야 함!!

 

* DFS 사용 시 시간 초과

DFS에 stack을 추가해 모든 경로를 구함

예를 들어 1에서 5번간의 모든 친구 경로를 찾음 -> (1, 3, 4, 5), (1, 4, 5) 2개의 경로를 찾음

이 중에서 경로가 작은 값을 최소 친구 탐색 수로 선택!

1부터 N까지 모든 친구에 대해 다 탐색함

경로를 불필요하게 다 구하고 계산하다 보니 시간 초과가 난 듯함ㅠㅠ 굳이 살펴보지 않아도 될 경로를 재귀를 통해 찾고 있으니...

 

실패한 DFS 코드

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static boolean[] visited;
	public static int[][] adjArray; 
	public static Stack<Integer> stack;
	public static int min;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		adjArray = new int[N+1][N+1];

		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			adjArray[a][b] = 1;
			adjArray[b][a] = 1;
		}

		int ans = 0;
		int ansCount = Integer.MAX_VALUE;
		
		for(int i = 1; i < N+1; i++) {
			stack = new Stack<>();
			visited = new boolean[N+1];
			int result = 0;
			
			for(int j = 1; j < N+1; j++) {
				if(i != j) {
					min = Integer.MAX_VALUE;
					dfs(i, j);
					result += (min-1); // 자기자신 -1 
				}
			}
			
			if(ansCount > result) {
				ans = i;
				ansCount = result;
			}
		}
		
		System.out.println(ans);


	}

	public static void dfs(int start, int end) {
		visited[start] = true;
		stack.push(start); // 스택에 값을 넣어줌

		if(start == end) { // 목표 노드에 왔다면
			min = Math.min(min, stack.size());
		}

		for(int i = 1; i <= adjArray.length-1; i++) {
			if(adjArray[start][i] == 1 && !visited[i]) {
				dfs(i, end);
				// dfs 후에 방문 노드를 false로 만들어주어 해당 노드를 방문하지 않은 것으로 해줌 -> 모든 경로를 구하기 위함 
				visited[i] = false; 
			}
		}

		stack.pop(); //dfs 빠져 나올땐 pop()
	}

}

풀이

친구 관계를 인접 리스트나 인접 행렬로 만든 다음에 1번부터 N번까지의 친구들을 모두 BFS 탐색하며 몇 번 만에 친구관계가 성립하는지 구한다.

구해진 값들을 모두 더해서 케빈 베이컨 수를 만든다.

N까지의 친구 중 가장 작은 케빈 베이컨 수를 가진 친구의 번호를 출력한다. (중복 시 가장 작은 번호)

 

BFS 함수에서 start, find 변수로 시작과 종료 정점을 지정해, start부터 find 정점을 찾을 때까지 BFS 수행

BFS 탐색 시 int [] count 1차원 배열을 이용해 인접한 정점을 찾을 때마다(한 칸씩 너비를 늘려나갈 때마다) 해당 정점의 값을 +1 해줌

start == find로 정점을 찾았다면, check [find]에 있는 값이 바로 start부터 시작해 find까지 최소로 이동한 거리

즉, 최소로 친구 단계를 거치는 값이다.

 

import java.util.Iterator;

public static int bfs(int start, int find, int cnt) {
	Queue<Integer> queue = new LinkedList<>();
	queue.add(start);
	visited[start] = true;

	while(!queue.isEmpty()) {
		int cur = queue.poll();	

		Iterator<Integer> iter = adjList[cur].iterator();
		while(iter.hasNext()) {

			int next = iter.next();

			if(!visited[next]) { 
				// BFS를 수행하며 한 칸씩 너비를 늘려나갈때마다 1씩 추가됨 
				// 최소 거리 측정을 위함 ex) 1->5의 경우 1,3,4,5가 아니라 1,4,5를 거르기 위함
				check[next] = check[cur] + 1; 

				if(next == find) { // 종료 정점 
					return check[next]; // 최소 친구 단계의 합 
				}

				visited[next] = true; 
				queue.add(next); 
			} 
		}
	}
	return 0;
}

전체 코드

/**
 * @author Minha Gwon
 * @date 2021. 1. 21.
 * 케빈 베이컨의 6단계 법칙
 * https://www.acmicpc.net/problem/1389
 */

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static LinkedList<Integer>[] adjList;
	public static boolean[] visited;
	public static int[] check; // BFS 수행시 이동 거리(탐색 너비) 측정 

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		adjList = new LinkedList[N+1];
		for(int i= 1; i < N+1; i++) {
			adjList[i] = new LinkedList<>();
		}

		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			adjList[a].add(b);
			adjList[b].add(a);
		}

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

		for(int i = 1; i < N+1; i++) {
			int sum = 0;
			for(int j = 1; j < N+1; j++) {
				if(j != i) {
					visited = new boolean[N+1];
					check = new int[N+1];
					sum += bfs(i, j, 0);
				}
			}

			if(sum < min) {
				ans = i;
				min = Math.min(min, sum);
			}
		}

		System.out.println(ans);
	}

	public static int bfs(int start, int find, int cnt) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visited[start] = true;

		while(!queue.isEmpty()) {
			int cur = queue.poll();	

			Iterator<Integer> iter = adjList[cur].iterator();
			while(iter.hasNext()) {

				int next = iter.next();

				if(!visited[next]) { 
					// BFS를 수행하며 한 칸씩 너비를 늘려나갈때마다 1씩 추가됨 
					check[next] = check[cur] + 1; // 최소 거리 측정을 위함 ex) 1 -> 5의 경우 1,3,4,5가 아니라 1,4,5를 거르기 위함.

					if(next == find) { // 종료 정점 
						return check[next]; // 최소 친구 단계의 합 
					}

					visited[next] = true; 
					queue.add(next); 
				} 
			}
		}
		return 0;
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%231389/src/Main.java