1 minute read

문제

접근 방법

한 회원의 점수는 다른 회원들까지의 거리 중 최대값이라고 볼 수 있다. 따라서 모든 회원들에 대해 다른 회원들까지의 거리를 구해야 하므로 플로이드 워셜 알고리즘을 생각했다. $O(N^3)$이지만 회원의 수가 50명을 넘지 않기 때문에 가능하다고 판단하였다.

정답 코드


import sys
input = sys.stdin.readline

"""
한 회원의 점수는 다른 회원들까지의 거리 중 최대값이라고 볼 수 있다.

모든 회원들에 대해 다른 회원들까지의 거리를 구해야 하므로 플로이드 워셜 알고리즘을 생각했다.

O(N^3)이지만 회원의 수가 50명을 넘지 않기 때문에 가능하다.
"""

n = int(input())
distances = [[int(1e3)]*(n+1) for _ in range(n+1)]
while True:
  a,b = map(int, input().split())
  if a==-1 and b==-1:
    break
  distances[a][b]=1
  distances[b][a]=1


for i in range(n+1):
  distances[i][i] = 0

for mid_node in range(1,n+1):
  for start_node in range(1,n+1):
    for end_node in range(1,n+1):
      distances[start_node][end_node] = min(distances[start_node][end_node], distances[start_node][mid_node] + distances[mid_node][end_node])

# 각 사람들의 최대 거리를 구해야 하므로 1000 없앰
for i in range(n+1):
  for j in range(n+1):
    if distances[i][j] == 1000:
      distances[i][j] = 0

# 각 사람들의 자기 기준 다른 사람들까지의 최대 거리를 담는 리스트
ppl = [0]*(n+1)

for i in range(1,n+1):
  ppl[i] = max(distances[i])

# 회장 후보 값
min_val = min(ppl[1:])

score = min_val
num = 0
result = []
for i in range(n+1):
  if ppl[i] == min_val:
    num+=1
    result.append(i)

print(f"{score} {num}")
for r in result:
  print(r, end=' ')

You May Also Enjoy