백준 2660. 회장뽑기

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

플로이드-워셜 알고리즘 사용 풀이

n = int(input())
INF = float('inf')

dp = [[INF]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
    dp[i][i] = 0 # 자기자신과의 거리는 0

while True:
    a, b = map(int, input().split())
    if a == -1 and b == -1:
        break
    dp[a][b] = 1 # 무방향
    dp[b][a] = 1

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dp[i][j] = min(dp[i][k]+dp[k][j],dp[i][j]) # k를 거쳐가는거랑, 안거치는거랑 최솟값 갱신

scores = [0]
min_score = INF
for i in range(1, n+1):
    if max(dp[i][1:]) < min_score: # dp[i][1:]는 i와 다른 모든 회원들과의 최단거리 중 가장 큰 값! = i의 점수
        min_score = max(dp[i][1:])
    scores.append(max(dp[i][1:]))

cand = []
for i in range(1,n+1):
    if scores[i] == min_score:
        cand.append(i)

print(min_score, len(cand))
print(*cand)