[백준] 2660 파이썬

문제

---

• 백준 2660 (골드 5)

백준 2660

어제 풀었던 백준 1389 문제와 굉장히 유사한 문제였다.
각 회원별로 다른 사람과의 이어져있는 단계를 구해야 했다.
회원수가 50명 이하 시간 제한은 1초라 시간 제한은 널널한 문제였다.

내 코드

---

BFS를 활용하여서 코드를 작성하려다가 이틀 전에 공부한 플로이드-워셜 알고리즘을 사용하면 간단하게 풀릴 것 같아 활용하였다.
자기 자신과의 관계를 0으로 설정해주지 않아서 59%에서 오류가 발생하였다.
이를 적절하게 초기화해주니 해결되었다.

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

n = int(input())
score = [[10**9] * (n) for _ in range(n)]
for i in range(n):
    score[i][i]=0

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

for k in range(n):
    for a in range(n):
        for b in range(n):
            score[a][b] = min(score[a][b], score[a][k] + score[k][b])

for x in score:
    master.append(max(x))

ans = min(master)
print(ans, master.count(ans))

for i in range(n):
    if master[i]==ans:
        print(i + 1, end = " ")

출력을 조금 더 간결한 코드로 작성할 수 있을 것 같은데 고민해봐야겠다.
모든 노드의 최단 경로를 구하는 것이 필요한 문제에서 플로이드-워셜 알고리즘을 잘 활용해 보아야겠다.