아이디어:
플로이드-와샬 알고리즘을 이용하여 푸는 문제이다.
플로이드-와샬 알고리즘은 모든 정점 쌍에 대한 최단경로를 구할 수 있는 알고리즘으로, 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)
'알고리즘💻 > 벨만포드&플로이드와샬' 카테고리의 다른 글
BOJ 11780번: 플로이드 2 (0) | 2021.02.15 |
---|---|
BOJ 11404번: 플로이드 (0) | 2021.02.15 |
BOJ 11403번: 경로 찾기 (0) | 2021.02.15 |
BOJ 1865번: 웜홀 (0) | 2021.02.15 |
BOJ 11657번: 타임머신 (0) | 2021.02.15 |