백준 2660번 - 회장뽑기

회장뽑기 문제 바로 가기

풀이 날짜: 2026-03-22

baekjoon 알고리즘 문제 풀이

풀이 코드


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

INF = int(1e9)
n = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]

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

while True:
    a,b = map(int, input().split())
    if a == -1 and b == -1:
        break

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

score = [0] * (n+1)

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

min_score = min(score[1:])

answer = []
for i in range(1,n+1):
    if score[i] == min_score:
        answer.append(i)
print(min_score, len(answer))
print(*answer)

접근 방법

이 문제의 목표는 모든 회원 중에서 “회장 후보”를 찾는 것이며, 회장 후보는 다른 모든 회원과의 거리가 가장 가까운 사람으로 정의된다.

핵심 아이디어 - 점수 의미

각 회원의 점수는 “다른 모든 회원까지의 최단 거리 중 가장 큰 값”으로 정의된다. 즉, 특정 회원을 기준으로 다른 모든 회원까지 가는 데 필요한 최소 친구 단계 수를 구하고, 그중 가장 먼 거리 값을 그 회원의 점수로 삼는다. 이 값이 작을수록 다른 사람들과 가까운 관계를 유지하고 있다는 의미가 된다.

각 회원의 점수 계산

각 회원을 기준으로 다른 모든 회원까지의 최단 거리를 계산한다. 예를 들어 1번 회원은 2번까지는 1단계, 3번과 4번까지는 2단계, 5번까지는 3단계가 걸린다. 따라서 가장 먼 거리인 3이 1번의 점수가 된다. 같은 방식으로 계산하면 2번, 3번, 4번은 가장 먼 거리까지의 값이 모두 2이며, 5번은 다시 3이 된다.

전체 점수 정리

모든 회원의 점수를 정리하면 다음과 같다.

1번: 3, 2번: 2, 3번: 2, 4번: 2, 5번: 3 이 중 가장 작은 값은 2이며, 이 값을 가진 회원들이 회장 후보가 된다.

최종 결과 해석

최소 점수는 2이고, 해당 점수를 가진 회원은 2번, 3번, 4번 총 3명이다. 따라서 출력은 “2 3”과 “2 3 4”가 된다. 첫 번째 줄은 회장 후보의 점수와 후보 수를 의미하고, 두 번째 줄은 후보 회원 번호를 오름차순으로 나열한 것이다.

내가 헷갈렸던 포인트

이 문제는 단순히 최단 거리만 구하는 것이 아니라, 그 결과를 활용해 각 노드의 중심성을 판단하는 문제였다. 특히 플로이드 워셜을 통해 구한 거리 정보를 기반으로 최댓값을 활용하는 방식이 헷갈렸다.

Vienna sausage