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

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

 

# 백준 2660 회장뽑기
import sys
from collections import deque

input = sys.stdin.readline
N = int(input())  # 회원 수

# 친구 관계를 저장할 인접 리스트
graph = [[] for _ in range(N + 1)]

# 점수를 인덱스로 하여 회원 목록을 저장할 리스트
scores = [[] for _ in range(N + 1)]

# 친구 관계 입력 받기
while True:
    A, B = map(int, input().split())
    if A == -1 and B == -1:
        break
    graph[A].append(B)
    graph[B].append(A)

# 각 회원마다 BFS 수행하여 점수 계산
for i in range(1, N + 1):
    score = 0  # 회원 i의 최대 거리(점수)
    visited = [False for _ in range(N + 1)]  # 방문 여부 체크
    q = deque()
    q.append((i, score))  # (현재 회원, 거리)

    # BFS 시작
    while q:
        man, s = q.popleft()
        if not visited[man]:
            score = max(score, s)  # 가장 멀리 있는 친구까지의 거리 갱신
            visited[man] = True
            for another in graph[man]:  # 인접한 친구 탐색
                q.append((another, s + 1))

    # 모든 사람과 연결되어 있을 경우 (고립된 사람이 없는 경우)
    if sum(visited) == N:
        scores[score].append(i)  # 해당 점수에 회원 i 추가

# 점수가 가장 낮은 사람(가장 유력한 회장 후보) 출력
for i in range(1, N + 1):
    if scores[i]:  # 점수 i를 받은 사람이 있다면
        print(i, len(scores[i]))  # 최소 점수와 후보 수 출력
        print(*scores[i])  # 후보 번호 출력
        break  # 더 낮은 점수는 없으므로 종료

 

그래프를 통해 노드간의 관계를 파악하면 된다.