케빈 베이컨의 6단계 법칙에 따르면 지구에 있는 모든 사람은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계만에 이어질 수 있는지 계산하는 게임이다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다.
예를 들어 백준 온라인 저지의 유저가 5명, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구일 때를 생각해 보자.
- 1은 2까지 3을 이용해 2단계, 3까지 1단계, 4까지 1단계, 5까지 4를 이용해 2단계만에 알 수 있다. 따라서 케빈 베이컨의 수는 2 + 1 + 1 + 2 = 6이다.
- 2는 1까지 3을 이용해 2단계, 3까지 1단계, 4까지 3을 이용해 2단계, 5까지 3과 4를 이용해 3단계만에 알 수 있다. 따라서 케빈 베이컨의 수는 2 + 1 + 2 + 3 = 8이다.
- 3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 이용해 2단계만에 알 수 있다. 따라서 케빈 베이컨의 수는 1 + 1 + 1 + 2 = 5이다.
- 4는 1까지 1단계, 2까지 3을 이용해 2단계, 3까지 1단계, 5까지 1단계만에 알 수 있다. 따라서 케빈 베이컨의 수는 1 + 2 + 1 + 1 = 5이다.
- 5는 1까지 4를 이용해 2단계, 2까지 4와 3을 이용해 3단계, 3까지 4를 이용해 2단계, 4까지 1단계만에 알 수 있다. 따라서 케빈 베이컨의 수는 2 + 3 + 2 + 1 = 8이다.
즉 5명의 유저 중 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다. 위와 같이 백준 온라인 저지의 유저 수와 친구 관계가 입력으로 주어졌을 때 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.
(시간 제한 2초)
입력
1번째 줄에 유저의 수 N(2 ≤ N ≤ 100)과 친구 관계의 수 M(1 ≤ M ≤ 5,000)이 주어진다. 2번째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이뤄져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구라면 B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복돼 들어올 수도 있으며, 친구가 1명도 없는 사람은 없다. 또한 모든 사람은 친구 관계로 연결돼 있다. 사람의 번호는 1부터 N까지이고, 두 사람이 같은 번호일 경우는 없다.
출력
1번째 줄에 케빈 베이컨 수가 가장 적은 사람을 출력한다. 그런 사람이 여러 명일 때는 번호가 가장 작은 사람을 출력한다.
예제 입력
5 5 // 유저의 수, 친구 관계의 수
1 3
1 4
4 5
4 3
3 2
예제 출력
3
1단계 - 문제 분석하기
최대 유저 수가 100명으로 작기 때문에 플로이드-워셜 알고리즘으로 해결할 수 있다. 직접적인 친구 관계를 맺은 상태를 비용 1로 계산하고, 한 row의 합이 그 사람의 케빈 베이컨의 수가 된다.
2단계 - 손으로 풀어 보기
1 인접 행렬을 자기 자신이면 0, 아니면 충분히 큰 수로 초기화한다. 그 후 주어진 친구 관계를 인접 행렬에 저장한다.
2 플로이드-워셜 점화식을 수행하여 3중 for 문으로 중간 경로를 탐색한다.
- Math.min(D[S][E] , D[S][K] + D[K][S])
3 케빈 베이컨의 수(각 행의 합)를 비교해 가장 작은 수가 나온 행 번호를 정답으로 출력한다. 같은 수가 있을 때는 더 작은 행 번호를 출력한다.
3단계 - sudo코드 작성하기
N(유저 수) M(친구 관계 수)
distance(친구 관계 데이터 저장 인접 배열)
for(i -> N만큼 반복)
{
for(j -> N만큼 반복)
{
if(i == j)
{
distance[i][j]에 0 저장
}
else
{
distance[i][j]에 충분히 큰 수 저장
}
}
}
for(M만큼 반복)
{
친구 관계 데이터를 distance에 저장(양방향 에지로 저장, 가중치 1)
}
for(k -> N만큼 반복)
{
for(i -> N만큼 반복)
{
for(j -> N만큼 반복)
{
distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j])
}
}
}
MIN(충분히 큰 수)
for(i -> N만큼 반복)
{
for(j -> N만큼 반복)
{
각 배열의 값 합치기(i의 케빈 베이컨 수)
}
if(MIN > i의 케빈 베이컨 수)
{
MIN 값을 i의 케빈 베이컨 수로 저장
}
}
가장 작은 케빈 베이컨 수를 지니고 있는 i 출력.4단계 - 코드 구현하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Q63 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] distance = new int[N+1][N+1];
for(int i = 1; i < N+1; i++){
for(int j = 1; j < N+1; j++){
if(i == j)
distance[i][j] = 0;
else
distance[i][j] = 100000001;
}
}
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
distance[s][e] = 1;
distance[e][s] = 1;
}
for(int k = 1; k < N+1; k++){
for(int i = 1; i < N+1; i++){
for(int j = 1; j < N+1; j++){
if(distance[i][j] > distance[i][k] + distance[k][j])
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
int Min = Integer.MAX_VALUE;
int result = 0;
for(int i = 1; i < N+1; i++){
int Kevin = 0;
for(int j = 1; j < N+1; j++){
Kevin += distance[i][j];
}
if(Min > Kevin){
Min = Kevin;
result = i;
}
}
System.out.println(result);
br.close();
}
}
- Do it! 알고리즘 코딩테스트 자바 편
