2660. 회장뽑기 (Python)

2660번: 회장뽑기

 

풀이

 회원의 수가 50명을 넘지 않으므로 회원 모두에 대하여 bfs를 진행하여 각 회원의 점수를 구한다. bfs를 통해 얻은 점수를 키로 하는 딕셔너리를 사용하여 해당 점수에 대한 회원들의 리스트를 기록한다. 

 마지막에 최소 점수에 해당하는 회원들의 리스트를 딕셔너리에서 가져와서 정렬한 후 출력해 주면 된다.

 

코드

import sys
from collections import defaultdict
input = sys.stdin.readline

# n번 회원에 대하여 bfs
def bfs(n):
    q = [(n, 0)]
    visited = [False for _ in range(N+1)]
    visited[n] = True
    maxScore = 0 # n번 회원으로부터 가장 멀리 떨어져 있는 관계인 사람을 찾는다.

    while q:
        person, score = q.pop(0)
        maxScore = max(maxScore, score) # maxScore 업데이트

        for friend in relationships[person]:
            if visited[friend]:
                continue

            visited[friend] = True
            q.append((friend, score + 1))

    return maxScore


if __name__ == '__main__':
    N = int(input())  # 회원의 수
    relationships = [[] for _ in range(N+1)]  # 친구 관계
    minScore = float('INF') # 모든 회원의 점수 중에서 가장 적은 점수
    scoreDict = defaultdict(list) # scoreDict[score] : score 점수에 해당하는 회원들의 리스트 

    while True:
        a, b = map(int, input().split())

        if a == b == -1:
            break

        relationships[a].append(b)
        relationships[b].append(a)

    for i in range(1, N+1):
        score = bfs(i) # 모든 회원에 대하여 bfs
        minScore = min(minScore, score) # 얻은 점수 중에서 가장 적은 점수를 기록
        scoreDict[score].append(i) # i번 회원을 scoreDict[score]에 추가 

    print(minScore, len(scoreDict[minScore])) 

    for i in sorted(scoreDict[minScore]):
        print(i, end=' ')