코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 친구가 한 명도 없는 사람 X
// 양방향 관계 A -> B, B -> A는 하나의 관계
// 시작 지점 X, 모두 방문 O -> 플로이드 워셜
// 번호는 1부터 N까지
class Main {
static int N, M; // 유저의 수, 관계의 수
static int[][] hi;
static final int INF = 123456789;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 초기 테이블 초기화 (인덱스 1 ~ N)
hi = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) {
hi[i][j] = 0; // 자신과의 관계는 가중치 0
} else {
hi[i][j] = INF;
}
}
}
// 관계 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
// 양방향 관계
hi[A][B] = 1;
hi[B][A] = 1;
}
// 플로이드 워셜
for (int k = 1; k <= N; k++) { // 경유 노드
for (int i = 1; i <= N; i++) { // 출발 노드
for (int j = 1; j <= N; j++) { // 도착 노드
hi[i][j] = Math.min(hi[i][j], hi[i][k] + hi[k][j]); // 비교해서 더 짧은 경로로 갱신
}
}
}
int answer = 0;
int value = INF;
// 케빈 베이컨 수 계산
for (int i = 1; i <= N; i++) {
int sum = 0;
for (int j = 1; j <= N; j++) {
sum += hi[i][j];
}
// 최솟값 갱신
if (sum < value) {
value = sum;
answer = i;
}
}
System.out.println(answer);
}
}
Java
복사
1.
친구 없는 사람은 없다
2.
인덱스 1~N까지
3.
모두 방문하여 가중치를 합산해야함
위에 3가지가 포인트인 것 같고, 모든 노드를 방문해서 합산 후, 최솟값을 구해야하기 때문에 모든 노드에 대해 bfs를 수행하던가 아니면 플로이드 워셜로 간단하게 풀 수 있다.
나는 플로이드 워셜로 풀었는데, 확실히 공식만 외우고 있으면 이차원 배열써서 플로이드 워셜로 푸는게 많이 편한 것 같긴 하다. 내일은 똑같은 문제 bfs로 풀어볼 예정
중간에 StringToknizer 초기화해주는걸 까먹어서 계속 런타임 에러가 났었다..
(for문 돌릴때 초기화해주는거 잊지말자!!)
공식 생각이 안나서 여기 참고
