[백준] 1389번 케빈 베이컨의 6단계 법칙 (그래프_Java)

다양한 풀이방법이 존재하는 문제!

 

BFS풀이도 있고, 플로이드-워셜 등

많은 풀이가 있었는데,

나는 인접행렬로 풀었다!

 

플로이드-워셜도 정리 한 번 해야지!

 

---

문제

 

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

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

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 인접행렬

인접행렬을 만든 후, 3단 반복문을 통해 서로의 거리를 탐색했다.

만약 n값이 더 컸으며 다른 방법을 써야겠지만, n의 최대가 100이라 무난하게 통과했다.

 

풀이과정

1.

유저의 수 n과, 관계의 수 m을 입력받는다.

 

2.

2차원 배열 map을 생성 후, 관계를 입력받고 값을 map에 저장한다.

만약 1과 3이 친구라면, map[1][3]의 값과 map[3][1]의 값은 1이 된다.

 

3.

이제 인접행렬을 탐색해야 한다.

i는 현재 탐색할 사람이다. j는 i와 관계가 있는 사람이다.

만약 map[i][j]의 값이 0이 아니라면, 둘은 서로 관계가 있다. 그럼 i는 j를 통해 다른 사람의 관계도 만들 수 있다.

1부터 n+1까지 새로운 반복문을 통해 새롭게 관계를 맺을 수 있는 사람이 있는지 봐야 한다.

i가 j를 통해 k와 연결이 되면, i와 k와의 관계는 i와 j와의 관계 + j와 k와의 관계가 된다.

 

4.

이미 i와 k의 관계 값이 0이 아니라면, 새로운 값이 원래 값보다 더 작은지 확인하고 갱신한다.

만약 i와 k의 관계 값이 0이라면, map[i][j] + map[j][k]로 갱신한다.

 

이 때, i와 k의 관계값은 k와 i의 관계값과 동일하므로, map[k][i]도 갱신해준다.

 

5.

친구들과의 관계가 가장 작은 값을 구하고, 작은 사람이 여러명이라면 맨 앞사람을 출력한

 

 

 

---

코드

 

import java.util.*;

public class Test_1389_케빈베이컨의6단계법칙 {

	static List<Integer>[] list;
	static int[][] map;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//유저의 수
		int n = sc.nextInt();
	
		//친구 관계의 수
		int m = sc.nextInt();
		
		//인접행렬 생성
		map = new int[n+1][n+1];
		for(int i=0; i<m; i++) {
			int f1 = sc.nextInt();
			int f2 = sc.nextInt();
			
			map[f1][f2]=1;
			map[f2][f1]=1;
		}
		
		//인접행렬 탐색
		for(int i=1; i<n+1; i++) {
			for(int j=1; j<n+1; j++) {
				if(i==j) continue;
				if(map[i][j]==0) continue;
				
				for(int k=1; k<n+1; k++) {
					if(i==k) continue;
					if(map[j][k]!=0 && map[i][k]!=0) {
						map[i][k] = Math.min(map[i][k], map[i][j]+map[j][k]); 
						map[k][i] = Math.min(map[i][k], map[i][j]+map[j][k]); 
					} 
					else if(map[j][k]!=0 && map[i][k]==0) {
						map[i][k] = map[i][j]+map[j][k]; 
						map[k][i] = map[i][j]+map[j][k]; 
					}
				}
			}
		}

		//가장 작은 수 구하기
		int min = Integer.MAX_VALUE;
		for(int i=1; i<n+1; i++) {
			int sum = 0;
			for(int j=1; j<n+1; j++) {
				sum+=map[i][j];
			}
			min = Math.min(min, sum);
		}
		

		int answer = 0;
		for(int i=1; i<n+1; i++) {
			int sum = 0;
			for(int j=1; j<n+1; j++) {
				sum+=map[i][j];
			}
			
			if(min==sum) {
				answer = i;
				break;
			}
		}
		
		//출력
		System.out.println(answer);
	}
}