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

접근 방법 🧐

다익스트라와 달리 시작 지점이 정해져 있지 않고, 모두와의 관계를 다 확인해야하니, 이것은 플로이드 워셜 문제다.

플로이드 워셜 오랜만~ 처음에 플로이드 워셜을 접했을 때는 너무 어려웠는데 점화식이 한 번 딱 이해가 간 순간, 다익스트라보다 쉬운 유형이 됐다.

• A와 B가 친구면, B와 A도 친구고, A와 B는 같을 수 없다
  ➡️ 양방향 관계, a == b이면 0 입력
  
  
• 친구가 한 명도 없는 사람은 없다. 모든 사람은 친구 관계로 연결되어 있다
  ➡️ 서로 어떻게든 이어지는 경로가 있다..?
  
  
• 케빈 베이컨 수 = 모두와의 관계에 도달하기 까지의 단계 합
  
  
• 케빈 베이컨 수가 같은 사람이 여러명이면 유저번호가 가장 작은 번호 출력

내가 쓴 코드 ✍️

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

public class Main {
	
	static int N, M;
	static int[][] rel;
	static final int INF = 999999999;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		rel = new int[N+1][N+1]; //1~N번이라 +1
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				rel[i][j] = INF;
				if(i == j) rel[i][j] = 0;
			}
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			rel[a][b] = 1; //양방향
			rel[b][a] = 1;
		}
		
		for(int k=1;k<=N;k++) { //중간지점
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					rel[i][j] = Math.min(rel[i][j], rel[i][k]+rel[k][j]);
				}
			}
		}
		int temp = INF;
		int result = 0;
		for(int i=1;i<=N;i++) {
			int total = 0;
			for(int j=1;j<=N;j++) {
				total += rel[i][j];
			}
			
			if(temp > total) { //커야하니까 작은 index 처리도 가능
				temp = total;
				result = i;
			}	
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
	}

}

느낀점 📖

현재 코드에서는 INF로 최댓값을 초기화 해줬지만, 처음 코드 썼을 때는 Integer.MAX_VALUE를 사용했다. 그랬더니 테스트케이스가 3이 아니라 1이 나오고, rel[i][j] 를 찍어보니 -21458393 이상한 음수가 나왔다.
이유를 몰라서 다른 스터디팀 친구들에게 물어보니, 약 21억인 integer의 max 값에 값을 추가로 더하면 overflow가 일어나면서 이상한 쓰레기값이 저장된다고 하더라
ㅎㅎ 전에 다른 문제에서 이와 같은 경우 경험햇는데 너무 오래된 일이라 기억이 안났다. 앞으로 쓸 때는 생각을 좀 해야겠다. 냅다 최댓값 초기화라고 MAX_VALUE 넣지 말구