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

 

www.acmicpc.net/problem/1389

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

아이디어:

플로이드-와샬 알고리즘을 이용하여 푸는 문제이다.

플로이드-와샬 알고리즘은 모든 정점 쌍에 대한 최단경로를 구할 수 있는 알고리즘으로, dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 를 이용하여 구현하면 되고 시간복잡도는 O(V^3)이다.

이 문제에서는 친구 관계를 입력받으면서 dist[A][B]=dist[B][A]=1을 넣고 이를 이용해서 플로이드 와샬 알고리즘을 이용하여 돌면서 각 쌍마다 케빈베이컨 수를 구한 후, 각각의 케빈 베이컨 수의 합을 구하면서 최솟값을 구한다.

 

import sys

N, M = map(int, sys.stdin.readline().split())
INF = 10**9
dist = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0 #자기자신까지의 거리
for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    dist[A][B] = 1
    dist[B][A] = 1

for k in range(1,N+1):
    for i in range(1, N+1):
         for j in range(1, N+1):
             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
num = INF
ans = 0
for i in range(1,N+1):
    temp = 0
    for j in range(1, N+1):
        temp += dist[i][j]
    if (num>temp):
        num = temp
        ans = i
print(ans)