[ 1058 ] [ Floyd ] 친구

https://www.acmicpc.net/problem/1058

1058번: 친구

---

풀이 과정

---

1. 2-친구가 되기 위해서는 간단하게 보면 직접 친구이거나, 한명의 친구를 거쳐서 친구이면 된다. 따라서 플로이드 알고리즘을 사용하여 거리 배열을 구한다.
   1. 직접 친구인 경우의 거리는 1이다.
   2. 한명의 친구를 거쳐서 친구인 경우의 거리는 2이다.
2. 각 사람별로 거리가 2 이하인 친구의 명수를 구해준 다음 최댓값을 구해준다.
3. (2)에서 구한 최댓값을 출력해 준다.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

matrix = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 'N':
            matrix[i][j] = int(10e9)
        else:
            matrix[i][j] = 1

for i in range(N):
    for j in range(N):
        for k in range(N):
            matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k])

answer = 0
for i in range(N):
    count = 0
    for j in range(N):
        if j != i and matrix[i][j] <= 2:
            count += 1
    answer = max(answer, count)


print(answer)