[白俊1389号]ケビン・ベーコンの六次法則-パイソン

質問リンク:https://www.acmicpc.net/problem/1389

質問する

ケビン・ベーコンの第6段階の法則によると、地球上の誰もが第6段階でお互いの知っている人に連絡することができる.ケビン・ベーコンゲームは、任意の2人が少なくともいくつかの段階で行うことができるゲームです.
例えば、全く関係ないような仁荷(インハ)大学の李ホホホ氏と西江(ソガン)大学のミン·セヒ氏は、何段階で続けられるだろうか.
千民浩と李浩浩は同じ学校に通っている.千民浩と崔伯俊はBaekjoonオンラインJudgeを通じて知り合った.崔柏俊は金善英とともにスターリングリンクを創設した.金善英と金道は現在、同じ学校のサークルに所属している.金道現と閔世熙は同じ学校に通っていて、知り合いだった.李江浩(イ·ガンホ)、千民浩(チョン·ミンホ)、崔伯俊(チェ·ボジュン)、金善英(キム·ソンヨン)、金道賢(キム·ドヒョン)、閔世煕(ミン·セヒ)のように、5段階だけを経ればいいということだ.
ケビン・ベーコンは、アメリカのハリウッド映画スターたちがケビン・ベーコンゲームを一緒に遊ぶときに現れる段階の総和が最も少ない人だという.
今日BaekjoonオンラインJudgeのプレイヤーの中で、ケビンベーコンの数が一番少ない人を探しています.Kevinベーコンの数は、すべての人とKevinベーコンゲームをしているときに現れる段階の和です.
例えば、BOJのプレイヤーは5名、1と3、1と4、2と3、3と4、4と5が友人であると仮定します.
1は2〜3が2段階、3〜1段階、4〜1段階、5〜4が2段階で分かる.したがって、Kevinベーコンの数は2+1+1+2=6である.
2は、1〜3が2段階、3〜1段階、4〜3が2段階、5〜3及び4が3段階を通過する.したがって、Kevinベーコンの数は2+1+2+3=8である.
3は1から1段階、2から1段階、4から1段階、5から4は2段階しか知らない.したがって、Kevinベーコンの数は1+1+1+2=5である.
4 1から1段階、2から3、2段階、3から1段階、5から1段階でわかります.4のケビンベーコンの数は1+2+1+1=5である.
最後の5は1〜4〜2段階、2〜4及び3は3段階、3〜4は2段階、4〜1段階を通過すれば分かる.5のケビンベーコンの数は2+3+2+1=8です.
5人のプレイヤーの中で、ケビンベーコンの数が最も少ないのは3と4です.
BOJプレイヤーの数と友人関係を入力すると、最も少ないケビンベーコンを探すプログラムを作成してください.

入力

第1行は、ユーザ数N(2≦N≦100)と、親友関係数M(1≦M≦5000)を与える.2行目から、M行には友人関係があります.友人関係はAとBからなり、AとBが友人であることを意味する.AとBが友達なら、BとAも友達で、AとBは同じことはありません.友達関係が繰り返されるかもしれませんが、いない友達は一人もいません.また、誰もが友達の関係でつながっています.人の番号は1からNで、二人は同じ番号を持っていません.

しゅつりょく

1行目の出力BOJプレイヤーの中でケビンベーコンの数が一番小さい人.このような人が複数いれば、出力数が一番小さい人です.

import sys
input=sys.stdin.readline

INF=int(1e9)

n,m=map(int,input().split())
graph=[[INF]*(n+1) for _ in range(n+1)]

# 자기 자신으로 가는비용은 0으로
for i in range(1, n+1):
  for j in range(1,n+1):
    if i==j:
      graph[i][j]=0

for _ in range(m):
  a,b=map(int,input().split())
  graph[a][b]=1
  graph[b][a]=1

# 플로이드 워셜 알고리즘 수행
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j])

result=[]
min_val=INF
min_person=0
# 각 유저의 케빈 베이컨의 수를 result에 넣어줌
for i in range(1, n+1):
  sum=0
  for j in range(1,n+1):
    sum+=graph[i][j]
  result.append(sum)

# 가장 작은 케빈 베이컨 수 가진 사람의 인덱스 찾기
for i in range(n):
  if result[i]<min_val:
    min_val=result[i]
    min_person=i

print(min_person+1)

floydwalshアルゴリズムを学習したことを記念して,解答を行った.