# BOJ - 1389 - 케빈 베이컨의 6단계 법칙

Updated:

```
import sys
def solution():
N, M = map(int, sys.stdin.readline().split())
relation = [[10000 for _ in range(N)] for _ in range(N)]
for _ in range(M):
start, end = map(int, sys.stdin.readline().split())
relation[start - 1][end - 1] = 1
relation[end - 1][start - 1] = 1
for k in range(N):
for i in range(N):
for j in range(N):
if relation[i][j] > relation[i][k] + relation[k][j]:
relation[i][j] = relation[i][k] + relation[k][j]
minRelation = 314159265
ret = 0
for idx, rel in enumerate(relation):
val = sum(rel)
if val < minRelation:
minRelation = val
ret = idx
print(ret+1)
solution()
```

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

## Leave a comment