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

 

https://www.acmicpc.net/problem/1389

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

 

해당 문제는 플로이트 와샬 알고리즘을 알고 있다면 간단히 풀수 있는 문제이다.

 

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리(혹은 최소비용)를 구할때 사용하는 알고리즘으로

 

거쳐가는 정점의 합산값과 혹은 이미 구해진 값을 비교하는 과정을 통해 최소값을 구해 정점에서 정점으로의 최소값을

구해낸다는 알고리즘이다.

 

즉 정점 i 에서 j로 이동하는 최단거리를 구하려할때

i >> j 의 값 과 i >> k + k >> j 의 최단거리의 합 을 비교 갱신하는 과정을 통해 최단거리를 구할수 있다.

 

보다 자세한 설명은 아래 링크를 참고하도록 한다.

 

 

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

 

다시 문제로 돌아가서 예제를 살펴보면,

 

다음과 같은 양방향 그래프로 표현이 가능한것을 알수 있다.

 

이를 인접행렬로 표현한다면,

 

	1	2	3	4	5
1	0		1	1
2		0	1
3	1	1	0	1
4	1		1	0	1
5				1	0

 

양방향 그래프 이므로 다음과 같이 대칭의 형태로 표현할수 있다.

 

문제에서 원하는것은 케빈베이컨의 수가  가장 작은사람 즉 각 행 또는 열에 대해 합을 구했을때

최소값을 갖는 행 또는 열을 구하면 되는것이다.

 

이제 남은 건 인접행렬의 빈칸을 플로이드 와샬 알고리즘을 사용해 채우고, 순회하면서 최소값을 구하면 되는것이다.

 

플로이드 와샬 알고리즘을 사용해 빈칸을 채우는 과정은 다음과 같다.

 

현재 1행 2열의 빈칸을 채우려고 하는경우,

즉 1 >> 2 로 이동하는 최단거리는 1 >> 3 >> 2 로 이동해야 최단거리이므로 2가된다.

 

1행 5열의 빈칸을 채우려고 하는 경우 역시

1 >> 5 로 이동하는 최단거리 이므로 1 >> 4 >> 5 로 이동해야 최단거리이므로 2가 됨을 알수 있고,

 

2행 5열의 경우 2 >> 3 >> 4 >> 5 이므로 최단거리가 3이 됨을 알수 있다.

 

이 과정을 모두 수행후 표를 다 채우면 다음과 같은 표를 얻을수 있다.

 

 

	1	2	3	4	5
1	0	2	1	1	2
2	2	0	1	2	3
3	1	1	0	1	2
4	1	2	1	0	1
5	2	3	2	1	0

 

이후 각 행의 합을 비교후 최소값을 갖는 행은 3행,4행임을 알수 있고 우선한 행을 답으로 처리하면 된다.

 

이를 코드로 표현하면 다음과 같이 표현할수 있다.

 

package boj2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj1389 {

	/*
	 * 양방향 그래프
	 * 기본적으로 주어지는 친구관계 인접행렬에 입력
	 * (a,a) 같은 자기자신은 0 입력
	 * 인접행렬 값중 null 값인 값들에 대해 최단거리로 값 구하기 --> 플로이드와샬
	 * 각 행에 대해 총합 구한뒤 최소값에 해당하는 행 리턴
	 */
	
	static Integer[][] metrix;
	static int n,m;
	
	static void init(int a, int b) {
		metrix[a][b] = metrix[b][a] = 1;
		metrix[a][a] = 0;
		metrix[b][b] = 0;
	}
	
	static void floyd() {
		for(int k = 1; k <= n; k++) {
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					if(metrix[i][k] != null && metrix[k][j] != null) {
						int dis = metrix[i][k] + metrix[k][j];
						if(metrix[i][j] == null) {
							metrix[i][j] = dis;
						}else {
							metrix[i][j] = Math.min(metrix[i][j], dis);
						}						
					}
				}
			}			
		}
	}
	
	static int getMin() {
		int min = Integer.MAX_VALUE;
		int idx = 0;
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			sum = 0;
			for(int j = 1; j <= n; j++) {
				sum += metrix[i][j];
			}
			if(min > sum) {
				min = sum;
				idx = i;
			}
		}
		return idx;
	}
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		metrix = new Integer[n + 1][n + 1];
		while(m-- > 0) {
			st = new StringTokenizer(in.readLine()," ");
			init(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
		}
		in.close();
		
		floyd();
		
		System.out.print(getMin());
	}
	
}