[백준] 1389 케빈 베이컨의 6단계 법칙

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

 

boj.kr

풀이

N이 100 이하이므로 플로이드-와샬 알고리즘을 사용하면 쉽게 해결할 수 있다. 플로이드 와샬 알고리즘을 사용해 친구들간의 거리를 구한 뒤, 가장 작은 케빈 베이컨 수를 가진 친구의 번호를 출력하면 된다.

코드

C++

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;
int n, m;
vector<vector<int>> adj;

void floyd_warshall() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (adj[i][j] > adj[i][k] + adj[k][j])
                    adj[i][j] = adj[i][k] + adj[k][j];

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    adj = vector<vector<int>>(n + 1, vector<int>(n + 1, INF));

    for (int i = 1; i <= n; i++) adj[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }

    floyd_warshall();

    int count = INF;
    int idx;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            cnt += adj[i][j];
        if (count > cnt) {
            count = cnt;
            idx = i;
        }
    }
    cout << idx << '\n';
    return 0;
}

Java

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int n, m;
    public static int[][] adj;
    public static final int INF = 1000000000;

    public static void floydWarshall() {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (adj[i][j] > adj[i][k] + adj[k][j])
                        adj[i][j] = adj[i][k] + adj[k][j];
    }

    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());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        adj = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) Arrays.fill(adj[i], INF);

        for (int i = 1; i <= n; i++) adj[i][i] = 0;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[a][b] = 1;
            adj[b][a] = 1;
        }

        floydWarshall();

        int count = INF;
        int idx = 0;
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 1; j <= n; j++)
                cnt += adj[i][j];
            if (count > cnt) {
                count = cnt;
                idx = i;
            }
        }
        bw.write(String.valueOf(idx));
        bw.flush();
    }
}

Python3

import sys

input = sys.stdin.readline

INF = 1e9
n, m = map(int, input().rstrip().split())
adj = [[INF] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().rstrip().split())
    adj[a][b] = 1
    adj[b][a] = 1

for i in range(1, n + 1):
    adj[i][i] = 0


def floyd_warshall():
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if adj[i][j] > adj[i][k] + adj[k][j]:
                    adj[i][j] = adj[i][k] + adj[k][j]


floyd_warshall()

count = INF
idx = 0
for i in range(1, n + 1):
    cnt = 0
    for j in range(1, n + 1):
        cnt += adj[i][j]
    if count > cnt:
        count = cnt
        idx = i
print(idx)