[Python/파이썬] 백준 2660번 회장뽑기

2660번: 회장뽑기

 

코드

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

# Floyd-Warshall
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dist[i][j] > dist[i][k]+dist[k][j]:
                dist[i][j] = dist[i][k]+dist[k][j]

cm, cm_score = [], 50
for i in range(1, n+1):
    score = 0
    for j in range(1, n+1):
        score = max(score, dist[i][j])
    if score < cm_score:
        cm = [i]
        cm_score = score
    elif score == cm_score:
        cm.append(i)

print(cm_score, len(cm))
print(*cm)

 

두 회원이 서로 친구일 때 둘 사이의 거리를 1이라고 할 때, 각 회원의 점수는 자신으로부터 가장 거리가 먼 사람과의 거리이다. 그러니까 누가 가장 낮은 점수를 갖고 있는지 알려면 모든 회원 간의 거리를 구해야 한다.

 

플로이드 워셜(Floyd-Warshall) 알고리즘을 사용하면 모든 정점들간의 거리를 구할 수 있다. 이 알고리즘을 이용하여 모든 회원 간의 거리를 구한 뒤, 가장 먼 사람과의 거리가 작은 사람들이 바로 회장 후보이다.