백준_1389_케빈 베이컨의 6단계 법칙

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

1389번: 케빈 베이컨의 6단계 법칙

해결 방법

> 각 사람들을 하나의 노드하고 생각하였다.

> 케빈의 베이컨 수는 각 노드에서 나머지 노드까지의 최단 거리의 합이다.

> 플로이드 워셜을 활용한다.

> 2차원 배열의 가로줄의 합이 케빈의 베이컨 수가 된다.

 

코드

user, friends_num = map(int,input().split())

#친구관계

relation = [[100 for i in range(user)]for i in range(user)]

 

for i in range(friends_num):

    one, two = map(int, input().split())

    relation[one-1][two-1] = 1

    relation[two-1][one-1] = 1

#플로이드 워셜

for k in range(user):

    for i in range(user):

        for j in range(user):

            if i == j:

                pass

            else:

                relation[i][j] = min(relation[i][k] + relation[k][j], relation[i][j])

 

final_relation = []

for i in relation:

    final_relation.append(sum(i))

 

print(final_relation.index(min(final_relation)) + 1)