실버 I

💡문제 분석 요약

floyd-warshall

플루이드-워셜

💡알고리즘 설계

플루이드 워셔로 모든 친구와 몇 단계로 알 수 있는지를 정리해야한다.

들어오는 관계를 통해 INF로 초기화한 bacon 배열에 관계를 1로 추가한다.

이후 플루이드 워셜 알고리즘을 통해, 관계의 최솟값을 넣는다.

다 정리되면, inf인 값은 관계가 없는 것으로 0으로 설정한 뒤 각 번호의 모든 값을 더하여 answer에 추가한다.

answer에 0번은 없으므로 [1:]로 슬라이스 한 뒤,

최솟값을 가지는 번호를 출력한다.

💡코드

import sys,math
input= sys.stdin.readline
n, m = map(int, input().split())
inf= math.inf
bacon = [[math.inf for _ in range(n+1)] for _ in range(n+1)]
answer = []
for _ in range(m):
    i,j = map(int,input().strip().split())
    bacon[i][j] = 1
    bacon[j][i] = 1
    
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            bacon[i][j] = min(bacon[i][j], bacon[i][k]+bacon[k][j])

for i in range(n+1):
    for j in range(n+1):
        if bacon[i][j]==inf:
            bacon[i][j] =0
    answer.append(sum(bacon[i]))
answer = answer[1:]

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

💡 헷갈린 이유

들어오는 값이 1~n이므로 배열을 range(n+1)로 설정해야 한다.