BOJ 1389 - 케빈 베이컨의 6단계 법칙 링크
(2022.11.08 기준 S1)
(치팅하면 평생 베이컨 못먹음)

문제

임의의 두 사람이 최소로 이어질 수 있는 단계 수가 베이컨이라고 했을 때, 베이컨의 수의 합이 가장 작은 사람 출력

알고리즘

N이 100 이하이고, 모든 사람마다 다른 모든 사람으로 이어지는 최단 거리를 찾아야 하므로 플로이드 워셜이 적합하다.

풀이

각 사람 간 베이컨의 수를 저장할 N * N 크기의 인접 행렬을 만들자. 친구 관계가 주어지기 전엔 모두 모르는 사람이므로 무한대로 초기화.
친구 관계가 주어지면 직접 친구 관계인 경우엔 베이컨의 수가 1이므로 1로 저장하자. 물론, 양방향으로.

그리고 플로이드 워셜을 돌리면 된다.
A와 B의 베이컨 수보다 A-C, C-B의 베이컨의 수가 작으면 갱신해주는 것이다.
모든 경유지를 생각하는 경우의 수에 따른 최단 거리를 구하는 것이 바로 플로이드 워셜이다.

for k in range(N): # 경유지
	for i in range(N):
    	for j in range(N):
        	bacon[i][j] = min(bacon[i][j], bacon[i][k] + bacon[k][j])

끝났다면 1번 사람부터 차례대로 베이컨의 합을 구해 답을 갱신하면 끝!

코드

import sys; input = sys.stdin.readline
from math import inf

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

# 초기 베이컨은 전부 무한대
matrix = [[inf] * (N + 1) for _ in range(N + 1)]

# 직접 친구 관계이면 베이컨은 1이다.
for _ in range(M):
    A, B = map(int, input().split())
    matrix[A][B] = 1
    matrix[B][A] = 1

# 플로이드 워셜
for k in range(1, N + 1): # 경유지
    matrix[k][k] = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            # 경유할 때의 베이컨이 더 작으면 경유하는 방향으로 바꾼다.
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

# 최소 베이컨의 수를 갱신하면서 정답을 구한다.
min_bacon = answer = inf
for i in range(1, N + 1):
    bacon = sum(matrix[i][1:]) # 0번은 없는 사람이고 베이컨의 수는 inf 이므로 제외
    if bacon < min_bacon:
        min_bacon = bacon
        answer = i

print(answer)

여담

정말 간단한 플로이드 워셜 문제.
입문으로 딱인 듯 하다.