코드
n = int(input())
dist = [[50]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
dist[i][i] = 0
while True:
a, b = map(int, input().split())
if a == -1 and b == -1:
break
dist[a][b] = 1
dist[b][a] = 1
# Floyd-Warshall
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if dist[i][j] > dist[i][k]+dist[k][j]:
dist[i][j] = dist[i][k]+dist[k][j]
cm, cm_score = [], 50
for i in range(1, n+1):
score = 0
for j in range(1, n+1):
score = max(score, dist[i][j])
if score < cm_score:
cm = [i]
cm_score = score
elif score == cm_score:
cm.append(i)
print(cm_score, len(cm))
print(*cm)
두 회원이 서로 친구일 때 둘 사이의 거리를 1이라고 할 때, 각 회원의 점수는 자신으로부터 가장 거리가 먼 사람과의 거리이다. 그러니까 누가 가장 낮은 점수를 갖고 있는지 알려면 모든 회원 간의 거리를 구해야 한다.
플로이드 워셜(Floyd-Warshall) 알고리즘을 사용하면 모든 정점들간의 거리를 구할 수 있다. 이 알고리즘을 이용하여 모든 회원 간의 거리를 구한 뒤, 가장 먼 사람과의 거리가 작은 사람들이 바로 회장 후보이다.
'문제풀이 > 최단경로' 카테고리의 다른 글
[Python/파이썬] SW Expert Academy 1249번 보급로 (0) | 2024.06.14 |
---|---|
[Python/파이썬] 백준 10282번 해킹 (0) | 2024.05.16 |
[Python/파이썬] 백준 17396번 백도어 (0) | 2024.04.14 |
[Python/파이썬] 백준 2458번 키 순서 (0) | 2024.04.12 |
[Python/파이썬] 백준 20007번 떡 돌리기 (0) | 2024.04.11 |