[백준] 2660 회장뽑기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

한 사람이 다른 모든 사람과의 관계 거리가 어떻게 되는지에 대한 정보를 모든 사람을 기준으로 하여 구하여야 했습니다.

처음에 BFS를 이용하여 다른 사람들과의 관계 거리를 구하려 하였으나, 사람의 수가 많아지는 경우에 사람 수에 맞게 BFS 탐색이 필요했습니다.

이러한 경우에 시간 초과 문제를 고려하게 되었고, 이 문제에 조금 더 적합할것 같은 플로이드 워셜을 이용하여 풀이하였습니다.

2) 알고리즘

• 플로이드 워셜

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                           # 사람 수
answers = [[1e10] * N for _ in range(N)]                # 사람들 가까운 정도

while True:
    a, b = map(int, sys.stdin.readline().split())       

    if a == -1:                                         # 입력이 음수이면 종료
        break
    
    answers[a-1][b-1] = 1                               # 두 사람은 친구 관계로 거리 1
    answers[b-1][a-1] = 1

for k in range(N):
    answers[k][k] = 0                                   # 본인은 거리 0으로 설정
    for i in range(N):
        for j in range(N):
            # 두 사람의 직접 관계와 누군가를 통하는 관계 중 더 짧은 거리 선택
            answers[i][j] = min(answers[i][j], answers[i][k] + answers[k][j])

min_length = 1e10                   # 가장 작은 회원 점수
min_li = set()                      # 회장 후보
for i in range(N):
    l = max(answers[i])             # 한 사람의 회원 점수

    if min_length < l:              # 회원 점수가 전체 최소값 보다 크다면
        continue                    # 다음 사람 탐색
    elif min_length > l:            # 최소값 갱신시 회장 후보 모두 제거
        min_li.clear()
        min_length = l
    min_li.add(i+1)                 # 회장 후보 추가

print(min_length, len(min_li))      # 출력
print(*sorted(min_li))

---

🔗 문제 링크

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

2660번: 회장뽑기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다