(백준) 1389 Kevin Bacon의 6단계 규칙 (Python)

https://www.acmicpc.net/problem/1389

1. 난이도 실버 1 ()

2. 문제 해결 방법

BFS나 Floyd-Warshall으로 해결할 수 있지만

Floyd Warhall을 사용하여 이 문제를 해결했습니다.

인접행렬을 이중 연결 리스트로 만들고 친구를 통해 도착한 횟수의 최소값을 인접행렬에 넣는다.

행렬의 각 행을 더한 후 최소값의 인덱스를 출력합니다.

3. 내가 작성한 코드

n,m = map(int, input().split()) #n 유저 m 친구관계
INF = int(1e9)

graph = ((INF) * (n+1) for _ in range(n+1))

result = () #케빈 베이컨 수 입력력

for i in range(1,n+1):
  for j in range(1,n+1):
    if i == j:
      graph(i)(j) = 0\

for i in range(m):
  a,b = map(int,input().split())
  graph(a)(b) = 1
  graph(b)(a) = 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))

for i in range(1,n+1):
  result.append(sum(graph(i)))

x = min(result)

print((result.index(x))+1)