[BOJ] 1389: 케빈 베이컨의 6단계 법칙 (JAVA)

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

 

풀이

 

양방향으로 이어져있는 노드들 사이에서, 예를들어 내가 1일때

1. 2~N 까지 갈 수 있는 최단거리를 구한 다음

2. 그 최단 거리들을 전부 합한게 1의 케빈 베이컨의 수

3. 1~N 의 케빈 베이컨의 수가 가장 작은 사람을 구하는 문제.

 

각 숫자까지의 최단거리를 기록해줘야 했다.

이전 숫자까지 간 거리 + 1 을 해준 것이 최단거리이기 때문.

 

노드간 최단경로를 구할 수 있는 알고리즘엔 플로이드워셜, 다익스트라, 벨만 포드 알고리즘이 있다고 알고있는데,

이건 다음주 중으로 공부해서 문제 풀어볼 생각이다.

 

 

package 백준renew;

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

public class 실버1_1389_케빈베이컨의법칙 {
	static int N, M, min;
	static int friendship[][];
	static int people[];
	static int tmp[];
	static boolean ok[];
	static int ans;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		friendship = new int[N][N];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			friendship[num1-1][num2-1] = 1;
			friendship[num2-1][num1-1] = 1;
		}
		
		people = new int[N];
		min = Integer.MAX_VALUE;
		for(int i=0; i<N; i++) {
			tmp = new int[N];
			ok = new boolean[N];
			Check(i);
		}
		
		ans = 0;
		Small();
		sb.append(ans+1);
		
		bw.write(sb.toString()); bw.close();
	}
	static void Small() {
		for(int i=0; i<N; i++) {
			min = Math.min(min, people[i]);
		}
		
		for(int i=0; i<N; i++) {
			if(people[i] == min) {
				ans = i;
				break;
			}
		}
	}
	static void Check(int x) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(x);
		ok[x] = true;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			for(int i=0; i<N; i++) {
				if(friendship[i][now] == 1 && friendship[now][i] == 1 && !ok[i]) {
					tmp[i] = tmp[now] + 1;
					q.offer(i);
					ok[i] = true;
				}else {
					continue;
				}
			}
		}
		
		for(int i=0; i<N; i++) {
			people[x] += tmp[i];
		}
	}
}