[BOJ] 1058번 친구 파이썬

풀이

#플로이드워셜

입력 받은 배열에 따라 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))