반응형
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
반응형
'코딩테스트 > 백준' 카테고리의 다른 글
[Java] 백준 1309 : 동물원 (0) | 2023.02.21 |
---|---|
[Java] 백준 1946 : 신입 사원 (0) | 2023.02.20 |
[Java] 백준 11660 : 구간 합 구하기 5 (0) | 2023.02.17 |
[Java] 백준 2538 : 영역 구하기 (0) | 2023.02.16 |
[Java] 백준 11286 : 절대값 힙 (0) | 2023.02.16 |
댓글