[백준]1389 케빈베이컨의6단계법칙 #플로이드와샬 정석

1. 풀이

플로이드와샬의 정석

k 포문이 돌아갈때 L[i][j]의 의미 : k정점까지 사용이 가능할 때 i에서 j까지의 최단거리

 

* 초기화시 주의할점

L[i][j]가 

(1) if i==j 이면 => 0

(2) if i!=j 이면 => inf

으로 초기화할것!

 

2. 소스코드

N,M=map(int,input().split())
maxNum=9876543210
L=[[maxNum for j in range(N+1)] for i in range(N+1)]

for i in range(1,M+1):
    a,b=map(int,input().split())
    L[a][b]=1
    L[b][a]=1
for i in range(1,N+1):
    L[i][i]=0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            temp=L[i][k] + L[k][j]
            if L[i][j]>temp:
                L[i][j]=temp

ansNum=maxNum
ans=0
for i in range(1,N+1):
    tempSum=sum(L[i][1:])
    if tempSum<ansNum:
        ansNum=tempSum
        ans=i
print(ans)