[백준 2660] 회장뽑기 - Python

문제 보기

 

[사용한 알고리즘]

플로이드-워셜(Floyld-Warshall)

 

[알고리즘]

1. 입력값을 이용해 무방향 그래프를 구현합니다.

2. 플로이드-워셜 알고리즘을 통해 각 회원들이 모든 회원가 친구가 되기 위한 최소 단계를 구합니다.

3. 각 회원 중 모든 회원가 친구가 되기 위한 최소 점수를 가진 회원들을 찾습니다.

4. 회장 후보의 점수와 후보의 수를 출력하고, 다음 줄에 회장 후보를 오름차순으로 모두 출력합니다.

 

[코드]

import sys


INF = 1e10


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    graph = [[INF for _ in range(n + 1)] for _ in range(n + 1)]

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

    while True:
        a, b = map(int, sys.stdin.readline().split())
        if a == -1 and b == -1:
            break
        else:
            graph[a][b] = 1
            graph[b][a] = 1

    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])

    # 회장 후보 점수 찾기
    min_score = INF
    for i in range(1, n + 1):
        min_score = min(min_score, max(graph[i][1:]))

    # min_score와 일치하는 인덱스 찾기
    candidate = []
    for i in range(1, n + 1):
        if min_score == max(graph[i][1:]):
            candidate.append(i)
    candidate.sort()

    print(min_score, len(candidate))
    print(" ".join(map(str, candidate)))