[BOJ/python] 1389: 케빈 베이컨의 6단계 법칙

문제

✔️ silver 1
그래프 이론
그래프 탐색
너비 우선 탐색
최단 경로
플로이드–워셜

문제 흐름

이 문제 역시 플로이드-워셜 알고리즘을 이용해 풀었다.
거리(가중치)가 1이고 방향이 없는 그래프에서 모든 노드에서 모든 노드로의 최단 거리를 구하는 식으로 진행했다.
구해진 최단거리 인접행렬에서 각 행별로 본인을 제외한 합을 구하면 해당 노드의 케빈 베이컨의 수가 되겠다.

코드

# 케빈 베이컨의 6단계 법칙
# graph

import sys
import pprint
input = sys.stdin.readline

def fw(g: list):
    n = len(g)
    for k in range(n):
        for u in range(n):
            for v in range(n):
                g[u][v] = min(g[u][v], g[u][k]+g[k][v])

if __name__ == "__main__":
    n, m = map(int, input().split())
    g = [ [float('inf') for i in range(n+1)] for ㅓ in range(n+1) ]
    for i in range(m):
        a, b = map(int, input().split())
        g[a][b] = 1
        g[b][a] = 1
    
    # pprint.pprint(g)
    fw(g)
    # pprint.pprint(g)

    min_value = float('inf')
    res = 0
    for i in range(1,n+1):
        tmp = 0
        for j in range(1,n+1):
            if i == j:
                continue
            tmp += g[i][j]
        if tmp < min_value:
            min_value = tmp
            res = i
    print(res)

마무리

내 풀이가 생각보다 시간이 오래걸려서 다른 사람들의 풀이도 참고했다.
다익스트라가 가장 많이 보였고, bfs를 문제에 맞게 응용한 풀이도 봤다.
다익스트라도 잘 기억이 안 나는데 조만간 복습해야겠다.