📕문제

[Baekjoon] 2660. 회장 뽑기

문제 설명

모임에서 회장을 선출하기 위해 후보를 선정하는 문제다.
회원들 간의 친구 여부가 주어졌을 때, 모든 회원과 친구인 회원은 1점, 모든 회원과 친구이거나 친구의 친구이면 2점, ... 이런 식으로 점수가 매겨진다.
가장 작은 점수인 회원이 회장이 된다 할 때, 회장의 점수와 회장 후보를 구하는 문제다.

---

📝풀이

import sys

read = sys.stdin.readline

N = int(read())

INF = sys.maxsize
graph = [[INF] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

while True:
    a, b = map(int, read().split())
    if a == -1:
        break
    graph[a-1][b-1] = graph[b-1][a-1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

levels = [max(filter(lambda x: x != INF, row)) for row in graph]
min_level = min(levels)
candidates = [i + 1 for i, level in enumerate(levels) if level == min_level]

print(min_level, len(candidates))
print(*candidates)

• 각 회원간의 친구 단계를 저장하기 위한 그래프(회원 수 * 회원 수)를 생성하고 거리를 INF로 설정.
  자기 자신까지의 거리는 0
• 친구 관계인 회원들의 단계를 1로 설정.
• 플로이드 워셜 알고리즘을 통해 모든 회원 간 최단 거리 계산.
• 가장 작은 점수 계산 후 후보자 선정.