친구
면접 대비시간 제한2초메모리 제한128 MB
N x N 친구 관계 행렬(N ≤ 50)이 주어질 때, 한 사람으로부터 두 단계 이내로 연결된 사람 수의 최댓값을 구합니다.
문제
두 사람 A와 B에 대해, A와 B가 직접 친구이거나 A와 B 모두와 친구인 사람 C가 존재하면 A는 B의 2-친구이다. 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다.
친구 관계가 주어졌을 때, 가장 유명한 사람의 2-친구 수를 출력하는 프로그램을 작성하시오.
친구 관계는 양방향이며, 어떤 사람도 자기 자신과는 친구가 아니다.
입력
첫째 줄에 사람의 수 N이 주어진다. N은 50 이하의 자연수이다.
다음 N개의 줄에는 친구 관계를 나타내는 길이 N의 문자열이 하나씩 주어진다. i번째 문자열의 j번째 문자가 Y이면 i번 사람과 j번 사람이 친구이고, N이면 친구가 아니다.
출력
첫째 줄에 가장 유명한 사람의 2-친구 수를 출력한다.