알고리즘연습/백준
[BOJ] 1058번 친구 파이썬
밈밈무
2022. 9. 1. 17:10
풀이
#플로이드워셜
입력 받은 배열에 따라 floyd계산 배열을 초기화해준 후 플로이드워셜을 수행한다.
모든 관계에 대한 값을 구한 후 floyd 계산 값이 1이상 2이하인 경우에 2-친구 수를 증가시키고 이 작업이 끝나면 최대값을 출력한다.
코드
N = int(input())
INF = 1e9
arr = [list(input().strip()) for _ in range(N)]
floyd = [[INF]*N for _ in range(N)]
result = [0 for _ in range(N)]
for i in range(N):
floyd[i][i]=0
for j in range(N):
if arr[i][j] == 'Y':
floyd[i][j] = 1
for k in range(N):
for i in range(N):
for j in range(N):
floyd[i][j] = min(floyd[i][j], floyd[i][k]+floyd[k][j])
for i in range(N):
for j in range(N):
if 0<floyd[i][j]<=2:
result[i]+=1
print(max(result))