[python3] 백준 1389 풀이 ( 케빈 베이컨의 6단계 법칙, 플로이드 워샬 )

이번 문제는 케빈 베이컨의 6단계 법칙이다. 케빈 베이컨이 할리우드의 핵 인싸라는 것을 인지하고 문제에 들어가자.

문제를 보자

문제가 상당히 길다. 읽어보면 그냥 네트워크 안에서 여러 사람들과 연결되어 있을때 모든 타인과 몇번만에 연결되어 있는지를 알아내어 최솟값을 가지는 즉, 허브 역할을 하는 사람을 구하면 된다.

문제를 잘 읽어보면 결국 N정점에서 N정점으로의 갈 때 얼마나 걸리는지를 구해야 한다. 그래야 한 노드에서 모든 노드에 방문할 때 케빈 베이컨의 수를 구할 수 있다. 즉, 모든 쌍 최단 거리 알고리즘을 사용하면 구할 수 있다.
모든 쌍 최단 거리 알고리즘의 대표적인 놈이 "플로이드 워샬"이다.
그러나! 플로이드 워샬은 O(N^3)이 걸리기 때문에 N값이 너무 크면 문제가 발생할 수 있다. 다행히 이번 문제에서 주어진 정점의 최댓값은 100이고 N^3을 한다면 1,000,000이기 때문에 100만의 연산으로도 답을 구할 수 있다. 따라서 플로이드 워샬로도 충분히 풀 수 있다는 생각이 들었다.

그럼 플로이드 워샬의 사용방법을 한번 복기해보자.

1. INF의 값으로 dp를 채운다.
2. dp[i][i]는 0으로 만든다.
3. k, i, j 순으로 루프를 돌린다.
4. 점화식은 dp[i][j] = min( dp[i][k] + dp[k][j], dp[i][j] )

이제 코드로 만들면 아래와 같다.

'''
N-> N 로 가는 경우의 수를 구하면된다.
즉, 모든쌍 최단거리 알고리즘을 사용한다.

N이 100이기 때문에 N^3을 해도 시간초과가 나진 않을것.
'''

INF = 1000
N,M = map(int, input().split())

dp = [[INF for i in range(N+1)] for i in range(N+1)]

adj = [[]for i in range(N+1)]
for _ in range(M):
    a,b = map(int, input().split())
    dp[a][b] = 1
    dp[b][a] = 1

    dp[a][a] = 0
    dp[b][b] = 0

# 플워는 kij
for k in range(1, N+1):
    for i in range(1,N+1):
        for j in range(1, N+1):
            dp[i][j] = min(dp[i][k]+dp[k][j], dp[i][j])

small = INF
smallF = 1
for i in range(N,0,-1):
    if small >= sum(dp[i][1:]):
        small = sum(dp[i][1:])
        smallF = i
print(smallF)

 

결론 : 플로이드 워샬에 INF들어가는거 까먹었었는데 다시 복기했다. 잊지말자