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

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

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

 

 

이 문제를 풀때, 플로이드 와샬의 개념을 적용하였다.

모든 정점에서 모든 정점까지의 최단거리

플로이드 와샬은 모든 정점에서 모든 정점까지의 최단거리를 구하는 것으로
한 정점에서 모든 정점까지의 거리를 구하는 다익스트라와는 다른 개념이다.

핵심은 거쳐가는 정점을 기준으로 최단거리를 구해야 한다는 것이다!!

 

 

- 인접행렬을 만들고,
   자기 자신(road[i][i])은 0, 나머지는 충분히 큰 수로 초기화 시켜준다.
- 직접 연결된 간선의 가중치를 1로 표시한다.
- 거쳐가는 노드를 기준으로 최단거리를 구한다.

road[i][j] = Math.min(road[i][j], road[i][k] + road[k][j]);

- 최단 거리의 합을 갖는 노드를 찾아 출력한다.

 

 

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

public class Main {
	static int N, M, road[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 유저수
		M = Integer.parseInt(st.nextToken()); // 관계 수

		// 초기화
		road = new int[N + 1][N + 1]; // 1번부터 사용하기 위해
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j)
					road[i][j] = 0; // 자기 자신으로 가는 경우
				else
					road[i][j] = 999999; // INF
			}
		}

		// 간선 연결
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			road[from][to] = road[to][from] = 1; // 직접 연결은 가중치 1
		}

		// 플로이드 와샬
		for (int k = 1; k <= N; k++) // 거쳐가는 노드
			for (int i = 1; i <= N; i++) // 시작 노드
				for (int j = 1; j <= N; j++) // 도착 노드
					road[i][j] = Math.min(road[i][j], road[i][k] + road[k][j]);


		// 최소 노드 찾기
		int min_node = Integer.MAX_VALUE;
		int min_road = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++) {
			int sum = 0;
			for (int j = 1; j <= N; j++)
				sum += road[i][j];

			if (min_road > sum) {
				min_node = i;
				min_road = sum;
			}
		}

		System.out.println(min_node);
	}

}