2660번 회장뽑기

문제

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

접근 방식

가장 먼 연결 관계가 그 사람의 점수가 된다는 걸 알 수 있다.

"몇 사람을 통하면 모두가 서로 알 수 있다"는 조건이 있기 때문에, 아예 연결이 안되는 경우는 없으므로, 그 비용이 무한으로 나올 순 없다.

단지 a에서 b의 관계가 아닌, a와 다른 모두와의 거리를 알아야 하기 때문에 플로이드 워셜로 접근할 수 있다.

graph라는 자료구조는 a -> b의 거리를 의미한다. 다만 여기서는 친구 관계는 양방향 연결 관계이기에, graph[a][b], graph[b][a]를 한번에 갱신하면 된다.

• graph[a] : a의 친구 관계로, 이 중 max값이 a의 점수라는 점을 활용하자

코드

from itertools import combinations

INF = int(1e9)

n = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]  # 친구 관계 그래프
for x in range(1, n + 1):  # 자기 자신은 0으로
    graph[x][x] = 0
while True:
    a, b = map(int, input().split())
    if a == -1 and b == -1:
        break
    graph[a][b] = 1
    graph[b][a] = 1

# F - W
for k in range(1, n + 1):
    for a, b in combinations([i for i in range(1, n + 1) if i != k], 2):  # combinations -> 양방향 한번에 갱신
        if a == b:
            continue
        graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
        graph[b][a] = min(graph[b][a], graph[b][k] + graph[k][a])

# 사람별 점수 계산
scores = [INF, ]  # 0번째 인덱스
for k in range(1, n + 1):
    scores.append(max(graph[k][1:]))

min_score = min(scores)  # 최소 점수 => 회장 후보
candidates = []  # 회장 후보
for i in range(1, n + 1):
    if scores[i] == min_score:
        candidates.append(i)

print(min_score, len(candidates))
print(*candidates)