No1389 케빈 베이컨의 6단계 법칙(플로이드 와샬 알고리즘)

2차원 배열로 두 점 사이의 간선의 유무를 입력.

플로이드 와샬 알고리즘을 통해 몇 번을 건너 도달할 수 있는지를 배열에 입력하여 답을 구하는 문제

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][N];
		boolean[] visit = new boolean[N];
		
		//map 초기화
        //자기 자신을 가리키는 경우 0, 초기값 최대로
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				map[i][j] = 987654321;
				if(i==j) map[i][j]=0;
			}
		}
		
        //다른 지점과 직접 연결되는 경우 1 입력
		for (int i = 0; i < M; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(str.nextToken());
			int b= Integer.parseInt(str.nextToken());	
			map[a-1][b-1]=1;
			map[b-1][a-1]=1;
		}

 

플로이드 와샬 알고리즘

		//플로이드 와샬 알고리즘
		//i와 j 사이에 직접 연결이 없어 값이 최대값일 경우 중간에 k를 들려 갈 수 있다면 i k를 지나는 값과 k j를 지나는 값을 더해준다.
        for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j] > map[i][k]+map[k][j]) {
						map[i][j]=map[i][k]+map[k][j];
					}
				}
			}
		}

완성된 소스 코드는 아래와 같다.

package com.yuk;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class No1389 {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][N];
		boolean[] visit = new boolean[N];
		
		//map 초기화
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				map[i][j] = 987654321;
				if(i==j) map[i][j]=0;
			}
		}
		
		for (int i = 0; i < M; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(str.nextToken());
			int b= Integer.parseInt(str.nextToken());	
			map[a-1][b-1]=1;
			map[b-1][a-1]=1;
		}
		
		//플로이드 와샬 알고리즘
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j] > map[i][k]+map[k][j]) {
						map[i][j]=map[i][k]+map[k][j];
					}
				}
			}
		}
		
		int res = 987654321;
		int idx = -1;
		
		for (int i = 0; i < map.length; i++) {
			int sum = 0;
			for (int j = 0; j < map[i].length; j++) {
				sum+=map[i][j];
			}
			
			if(res>sum) {
				res = sum;
				idx=i;
			}
		}
		
		System.out.println(idx+1);		
		
	}
}