[CLASS 3: 플로이드 워셜] 백준 1389 케빈 베이컨의 6단계 법칙

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

https://www.acmicpc.net/problem/1389

 

# 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, 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[][] arr = new int[N + 1][N + 1];
 
        // 초기값 설정
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = INF; // 기본적으로 연결 안 되어 있다고 생각 (즉, 초기 거리는 무한으로 둠)
 
                if (i == j) {
                    arr[i][j] = 0; // 자기 자신과의 거리는 0
                }
            }
        }
        
        // 간선의 방향이 양방향이어야 함.
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
 
            arr[x][y] = arr[y][x] = 1; // 두 사람 사이 거리는 1 (양방향 연결)
        }
 
        // 플로이드 워셜 알고리즘
        // : 모든 정점 i → j 사이의 최단 거리를 중간에 k를 거쳐 가는 방식으로 갱신
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // 최단경로 초기화
                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
 
        int min = INF; // 가장 작은 케빈 베이컨 수를 저장하기 위한 변수 min
        int user_num = -1; // result를 가진 유저의 번호를 저장하기 위한 변수 user_num
 
        // 케빈 베이컨의 수가 가장 작은 인덱스를 탐색
        for (int i = 1; i <= N; i++) {
            int total = 0;
            for (int j = 1; j <= N; j++) {
                total += arr[i][j]; // i번 유저의 케빈 베이컨 수
            }
 
            if (min > total) {
                min = total;
                user_num = i;
            }
        }
 
        bw.write(user_num + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

• 플로이드 워셜(Floyd-Warshall) : 모든 정점 간의 최단 거리를 구하는 DP 기반의 알고리즘으로, 시간복잡도는 O(N^3)이다.
• 플로이드 워셜은 모든 정점 i, j 사이에 대해 중간에 k를 거칠 경우 거리가 더 짧은지 확인하면서 갱신한다.(=주석 '플로이드 워셜 알고리즘' 부분) 반면에 BFS는 큐 기반의 그래프 탐색이다.

 

플로이드 워셜 VS BFS

플로이드 워셜 VS BFS

 

 

 

이 문제를 BFS로 풀면 아래와 같다.

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

public class Main {
    static int N, M;  // N: 유저 수, M: 친구 관계 수
    static ArrayList<Integer>[] graph;  // 친구 관계를 저장할 인접 리스트

    public static void main(String[] args) throws IOException {
        // 입력 받기 위한 BufferedReader
        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번 인덱스부터 시작)
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 친구 관계 입력 받기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);  // a와 b는 친구니까 서로 연결
            graph[b].add(a);  // 양방향 연결
        }

        int min = Integer.MAX_VALUE;  // 최소 케빈 베이컨 수를 저장할 변수
        int answer = 0;               // 케빈 베이컨 수가 최소인 사람의 번호

        // 각 유저를 시작점으로 BFS 실행
        for (int i = 1; i <= N; i++) {
            int result = bfs(i);  // i번 유저의 케빈 베이컨 수 계산
            if (result < min) {
                min = result;     // 더 작은 값이면 갱신
                answer = i;       // 해당 유저 번호도 저장
            }
        }

        // 결과 출력
        System.out.println(answer);
    }

    // BFS: start 유저를 시작으로 모든 유저까지의 거리 합 계산
    static int bfs(int start) {
        boolean[] visited = new boolean[N + 1]; // 방문 여부 체크
        int[] dist = new int[N + 1];            // 거리 배열: dist[i] = start → i 거리
        Queue<Integer> q = new LinkedList<>();  // BFS에 사용할 큐

        q.offer(start);       // 시작 노드 큐에 넣기
        visited[start] = true; // 방문 처리

        while (!q.isEmpty()) {
            int curr = q.poll(); // 현재 노드 꺼내기

            for (int next : graph[curr]) { // 인접한 친구들 순회
                if (!visited[next]) {      // 아직 방문하지 않은 친구라면
                    visited[next] = true;             // 방문 처리
                    dist[next] = dist[curr] + 1;      // 거리 = 이전 거리 + 1
                    q.offer(next);                   // 다음 탐색 대상으로 추가
                }
            }
        }

        // 거리 합산 (케빈 베이컨 수 계산)
        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += dist[i];
        }

        return sum; // start 유저의 케빈 베이컨 수 반환
    }
}

 

 

 

BFS와 플로이드 워셜 코드의 성능을 비교해보면 BFS가 약간 더 좋은 성능을 보이는 것을 알 수 있다.

이번 문제는 정점의 수가 적어 차이가 많지는 않지만 실제로 최단거리를 구하는 문제가 나온다면 BFS 알고리즘을 사용하는 것이 더 효율적일 가능성이 높다.

위는 BFS, 아래는 플로이드 워셜