BAEKJOON / 백준 - JAVA 1389번 케빈 베이컨의 6단계 법칙

2024.06.24기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 친구의 관계를 입력 받을 때, 유저 중 모든 친구와 제일 가까운 유저를 출력하는 문제입니다.

 

이 문제에 접근하기 위해서 플로이드 위셜 알고리즘을 통해 접근을 하였습니다.

 

플로이드 워셜 알고리즘

그래프 내 모든 정점 쌍의 최단 경로를 반복적으로 계산합니다.
두 정점 사이의 최단 경로가 어떤 중간 정점을 거쳐서 갈 때 더 잛은지를 확인하여 입력하는 방식입니다.

플로이드 위셜 알고리즘 작동 과정
1. 초기화
● 그래프의 인접 행렬 d를 사용합니다. 여기서 d[i][j]는 정점 i에서 정점 j로 가는 초기 가중치를 의미합니다.
● 만약 i에서 j로 직접적인 간선이 없다면 d[i][j]를 무한대로 설정합니다. 그러나 자기 자신으로의 경로는 0으로 설정합니다. (d[i][i] = 0)

2. 경로 업데이트
● 중간 점걸 k를 차례로 고려하면서, 경로 i → j를 업데이트 합니다.
● 새로운 경로의 비용은 d[i][j]와 d[i][k] + d[k][j] 중 더 작은 값으로 결정합니다.

 

예제를 통해서 문제를 이해하도록 하겠습니다.

// 예제
5 5
1 3
1 4
4 5
4 3
3 2

 

1. 입력받은 노드와 간선으로 최단 거리 테이블을 생성합니다.

1-1. 2차원 배열을 생성해 테이블의 정보를 입력해줍니다.

1-2. 무한을 가정한 값을 1000000이라고 가정을 하고 입력을 했습니다.

int[][] node = new int[n + 1][n + 1];
int max = 1000000; // 친구가 아닐 때

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) {
            node[i][j] = 0;
        } else {
            node[i][j] = max;
        }
    }
}

int f1, f2;
while (m-- > 0) {
    st = new StringTokenizer(br.readLine());
    f1 = Integer.parseInt(st.nextToken());
    f2 = Integer.parseInt(st.nextToken());

    // f1과 f2가 친구이면 둘 다 친구이기 때문에, 양방향으로 입력해줍니다.
    node[f1][f2] = 1;
    node[f2][f1] = 1;
}

 

2. 플로이드 워셜 알고리즘을 이용해 최단 거리를 테이블에 입력해줍니다.

for (int i = 1; i <= n; i++) { // 중간에 거칠 친구
    for (int j = 1; j <= n; j++) { // 시작 친구 번호
        for (int k = 1; k <= n; k++) { // 도착 친구 번호

            // 현재 거리와 중간에 친구를 걸치고 갔을 때 거리를 비교해 적은 수를 저장합니다.
            node[j][k] = Math.min(node[j][k], node[j][i] + node[i][k]);
        }
    }
}

 

2-1. 중간 지점이 1일때, 테이블의 변화 (i = 1)

d[2][3] = min(d[2][3], d[2][1] + d[1][3]) = min(1, 1000001) = 1

d[2][4] = min(d[2][4], d[2][1] + d[1][4]) = min(1000000, 1000001) = 1000000

.

.

.

 

중간 지점 1일 때는 아무런 변화가 일어나지 않습니다.

 

2-2. 중간 지점이 2일때, 테이블의 변화 (i = 2)

중간 지점 1과 똑같이 2일 때는 아무런 변화가 일어나지 않습니다.

 

2-3. 중간 지점이 3일때, 테이블의 변화 (i = 3)

d[1][2] = min(d[1][2], d[1][3] + d[3][2]) = min(1000000, 2) = 2

d[2][1] = min(d[2][1], d[2][3] + d[3][1]) = min(1000000, 2) = 2

d[2][4] = min(d[2][4], d[2][3] + d[3][4]) = min(1000000, 2) = 2

d[4][2] = min(d[4][2], d[4][3] + d[3][2]) = min(1000000, 2) = 2

 

중간 친구 3일 때는, 총 4개의 거리가 업데이트 됩니다.

 

2-4. 중간 지점이 4일때, 테이블의 변화 (i = 4)

d[1][5] = min(d[1][5], d[1][4] + d[4][5]) = min(1000000, 2) = 2
d[2][5] = min(d[2][5], d[2][4] + d[4][5]) = min(1000000, 3) = 3
d[3][5] = min(d[3][5], d[3][4] + d[4][5]) = min(1000000, 2) = 2
d[5][1] = min(d[5][1], d[5][4] + d[4][1]) = min(1000000, 2) = 2
d[5][2] = min(d[5][2], d[5][4] + d[4][2]) = min(1000000, 3) = 3
d[5][3] = min(d[5][3], d[5][4] + d[4][3]) = min(1000000, 2) = 2

중간 친구 4일 때는 총 6개의 거리가 업데이트 됩니다.

 

2-4. 중간 지점이 5일때, 테이블의 변화 (i = 5)

중간 친구가 5일 때에는 아무런 변화가 생기지 않습니다.

 

3. 이렇게 플로이드 위셜 알고리즘으로 업데이트된 테이블(이차원배열)을 통해 제일 작은 값의 인덱스를 구해줍니다.

int min = max, index = 0, sum;
for (int i = 1; i <= n; i++) {
    sum = 0;

    for (int j = 1; j <= n; j++) {
        sum += node[i][j];
    }

    if (min > sum) { // 최솟값이라면 번호와 간선의 수를 저장.
        min = sum;
        index = i;
    }
}

 

 

 

코드

package Main;

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

public class Main {
	
	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());
		int n = Integer.parseInt(st.nextToken()); // 유저의 수
		int m = Integer.parseInt(st.nextToken()); // 친구 관계의 수
		
		int[][] node = new int[n + 1][n + 1];
		int max = 1000000; // 친구가 아닐 때
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					node[i][j] = 0;
				} else {
					node[i][j] = max;
				}
			}
		}
		
		int f1, f2;
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			f1 = Integer.parseInt(st.nextToken());
			f2 = Integer.parseInt(st.nextToken());
			
			// f1과 f2가 친구이면 둘 다 친구이기 때문에, 양방향으로 입력해줍니다.
			node[f1][f2] = 1;
			node[f2][f1] = 1;
		}
		
		for (int i = 1; i <= n; i++) { // 중간에 거칠 친구
			for (int j = 1; j <= n; j++) { // 시작 친구 번호
				for (int k = 1; k <= n; k++) { // 도착 친구 번호
					
					// 현재 거리와 중간에 친구를 걸치고 갔을 때 거리를 비교해 적은 수를 저장합니다.
					node[j][k] = Math.min(node[j][k], node[j][i] + node[i][k]);
				}
			}
		}
		
		int min = max, index = 0, sum;
		for (int i = 1; i <= n; i++) {
			sum = 0;
			
			for (int j = 1; j <= n; j++) {
				sum += node[i][j];
			}
			
			if (min > sum) { // 최솟값이라면 번호와 간선의 수를 저장.
				min = sum;
				index = i;
			}
		}
		
		bw.write(Integer.toString(index));
		bw.flush();
		bw.close();
		br.close();
	}
}