[백준/Python] 2660. 회장뽑기

 

 

1. 백준 2660. 회장뽑기 (골5)

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

2660번: 회장뽑기

 

풀이

 

CODE

import math
import sys

input = sys.stdin.readline

n = int(input())
board = [[math.inf if i != j else 0 for j in range(n + 1)] for i in range(n + 1)]
a, b = map(int, input().split())
while a != -1:
    board[a][b] = 1
    board[b][a] = 1
    a, b = map(int, input().split())

    
def floyd_warchall(graph):
    # 플루이드-워셜 알고리즘
    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])

    return graph


result = floyd_warchall(board)
ans = {}
for i in range(1, n+1):
    ans[i] = max(result[i][1:])

min_score = min(ans.values())
print(min_score, list(ans.values()).count(min_score))
for key, value in ans.items():
    if value == min_score:
        print(key, end=' ')

• 플로이드 워셜로 풀면서 메모리 초과가 나지 않을까 걱정했는데 다행히 안났다.
• 오예~