[백준] 1389 케빈 베이컨의 6단계 법칙(python)

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

 

 

1. 난이도 실버1 (🥈) 

 

2. 문제 해결 방법

BFS로도 해결가능하고 플로이드-워셜로도 해결 가능하지만

 

플로이드워셜을 활용해서 이 문제를 해결했다.

 

인접행렬을 양방향 리스트로 만들어주고, 친구를 거쳐서 도달한 횟수 중 최솟값을 인접행렬에 넣는다.

 

행렬의 각 행을 더한 후, 제일 작은 값의 index를 출력하면 된다.

 

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)