[백준] 2660번 회장뽑기

💡문제접근

• 플로이드-워셜 알고리즘을 이용해서 문제를 해결

💡코드(메모리 : 31256KB, 시간 : 52ms)

import sys
input = sys.stdin.readline
INF = int(1e9)

N = int(input())
graph = [[INF] * (N+1) for _ in range(N+1)]
while True:
    a, b = map(int, input().strip().split())
    if a == -1 and b == -1:
        break
    graph[a][b] = 1
    graph[b][a] = 1

for a in range(1, N+1):
    for b in range(1, N+1):
        if a == b:
            graph[a][b] = 0

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if graph[a][b] > graph[a][k] + graph[k][b]:
                graph[a][b] = graph[a][k] + graph[k][b]

lst = []
for i in range(1, N+1):
    lst.append(max(graph[i][1:]))

# 점수가 가장 낮은 사람이 회장 후보로 선출
min_score = min(lst)
answer = []
print(min_score, lst.count(min_score))
for idx, val in enumerate(lst):
    if val == min_score:
        answer.append(idx+1)
print(*answer)

💡소요시간 : 37m