백준 문제 링크
회장뽑기
❓접근법
- 플로이드 워셜 알고리즘을 활용했다.
- 기본 플로이드 워셜 소스코드처럼
자기 자신에게 가는 비용은 0으로 지정하고
a, b 둘 다 -1이 나올 때까지
graph[a][b], graph[b][a]에 각각 1을 지정한다.
마지막으로 3중 반복문으로 최단 거리 테이블을 갱신해준다.- 이제 총합이 가장 작은 회원(회장 후보)을 찾아야한다.
answer = [] for i in range(1, n + 1): x = graph[i][1:] score = max(x) # 회장 후보의 점수 answer.append([sum(x), score, i]) # 총합, 회장 후보의 점수, 회장 후보를 넣어주고 정렬한다. answer = sorted(answer, key = lambda x: (x[0], x[1], x[2]))
- 가장 첫번째 회원이 바로 회장 후보이다.
고로 total_score = answer[0][0] # 총합
s = answer[0][1] # 회장 후보의 점수
이제 회장 후보가 누구누구 있는지 찾아야한다.total_score = answer[0][0] # 총합 s = answer[0][1] # 회장 후보의 점수 cnt = 0 result = [] for i in range(n): if answer[i][0] == total_score: cnt += 1 result.append(answer[i][2]) # 총합이 같을 때 후보의 수 + 1, result에 회장 후보가 누군지 넣기
- 마지막으로 회장 후보의 점수, 회장 후보의 수
회장 후보가 누군지 출력하면 끝!
👌🏻코드
n = int(input())
INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
while True:
a, b = map(int, input().split())
if a == b == -1:
break
graph[a][b] = 1
graph[b][a] = 1
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
answer = []
for i in range(1, n + 1):
x = graph[i][1:]
score = max(x)
answer.append([sum(x), score, i])
answer = sorted(answer, key = lambda x: (x[0], x[1], x[2]))
total_score = answer[0][0]
s = answer[0][1]
cnt = 0
result = []
for i in range(n):
if answer[i][0] == total_score:
cnt += 1
result.append(answer[i][2])
print(s, cnt)
print(* result)
.