2021.2.8 [백준] 케빈 베이컨의 6단계 법칙
최단 경로 알고리즘
Q
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
A
플로이드 워셜 알고리즘을 이용하여 풀었다.
코드
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for a in range(n + 1):
for b in range(n + 1):
if a == b:
graph[a][b] = 0
for _ in range(m):
x, y = map(int, input().split())
graph[x][y] = 1
graph[y][x] = 1 #양방향일때는 이거 빼먹으면 안된다!!
for k in range(n + 1): #플로이드 워셜 알고리즘 실행
for i in range(n + 1):
for j in range(n + 1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
sum_list = [0] * (n + 1)
for i in range(n + 1):
for j in range(n + 1):
if graph[i][j] < INF:
sum_list[i] += graph[i][j]
result = INF
for k in sum_list:
if k != 0:
result = min(result, k) #케빈 베이컨 수가 작은 사람의 값 찾기
print(sum_list.index(result)) #값에 해당하는 인덱스 위치 찾아서 출력