#286 백준 파이썬 [1389] 케빈 베이컨의 6단계 법칙 - 플로이드 와샬

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

 

SOLUTION

플로이드 와샬로 해결할 수 있는 문제.

https://claude-u.tistory.com/334 의 문제와 해결법과 동일하다.

출력부분만 부분 수정해준다.

PYTHON CODE

#입력
N, M = map(int, input().split())
friend_map = [[N for _ in range(N)] for _ in range(N)]

for _ in range(M):
    friend_A, friend_B = map(int, input().split())
    friend_map[friend_A-1][friend_B-1] = 1
    friend_map[friend_B-1][friend_A-1] = 1


#플로이드-워셜 알고리즘
for k in range(N): #경로 for문이 가장 상위 단계여야 누락되지 않는다
    for i in range(N):
        for j in range(N): 
            if i == j:
                friend_map[i][j] = 0 #자기 자신과는 친구가 되지 못한다
            else:
                friend_map[i][j] = min(friend_map[i][j],
                                       friend_map[i][k] + friend_map[k][j])


#출력
bacon = []
for row in friend_map:
    bacon.append(sum(row))
print(bacon.index(min(bacon)) + 1)