코딩테스트/백준

[Java] 백준 1389 : 케빈 베이컨의 6단계 법칙

플래시🦥 2023. 2. 20.
반응형
https://www.acmicpc.net/problem/1389
 

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

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻

www.acmicpc.net


 

import java.util.*;

public class Main {

	static int N,M;
	static int[][] arr;
	 private static int INF = 99999;
	 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();	// 유저의 수
		M = sc.nextInt();	// 친구 관계의 수 
		
		arr= new int[N+1][N+1];
		
		//초기화
		for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) arr[i][j]=INF;
            }
        }
		//관계 입력
		for(int i=0;i<M;i++) {
			int a= sc.nextInt();
			int b= sc.nextInt();
			arr[a][b]=arr[b][a]=1;
		}
		
		//플로이드-워셜
		 for (int k = 1; k <= N; k++) {
	            for (int i = 1; i <= N; i++) {
	                for (int j = 1; j <= N; j++) {
	                	arr[i][j] = Math.min(arr[i][j],arr[i][k]+arr[k][j]);
		        }
		    }
		}
		 
		 
		 int min = Integer.MAX_VALUE;
		 int minIdx = 0;

			for (int i = 1; i <= N; i++) {
				int sum = 0;
				for (int j = 1; j <= N; j++)
					sum += arr[i][j];

				if (min > sum) {
					min = sum;
					minIdx = i;
				}
			}

			System.out.println(minIdx);
		}// main()

	}// class Main

와... N이랑 M 이랑 혼동해서 사용해서... 20분 날렸다..

예제 입력이 N, M이 모두 5여서 결과는 맞게 나온 게 내 실수이다. 

다른 예제도 만들어서 입력 해볼걸..

괜히 이것저것 고쳐보고ㅋㅋㅋㅋ

다음부터 또 틀렸다고 하면 변수 사용도 꼭!!! 확인해 봐야겠다..

고뇌의 흔적ㅋㅋㅋ

 

728x90
반응형

댓글