2022-07-09 @이영훈
접근 방법
문제의 입력으로 받은 N * N의 2차원 그래프를 friends 로 선언합니다
그리고 직접 친구이거나 k 친구를 거쳐 친구인지까지 확인하는 2-친구 목록을 connected 변수로 선언합니다. 처음에는 0으로 초기화 합니다.
그리고 플로이드-워셜 알고리즘을 사용하여 2-친구 목록(connected)를 업데이트 합니다.
2-친구 목록 (connected)의 각 행의 합은 그 사람의 친구 수입니다. 따라서 각 행의 합 중 가장 큰 수를 답으로 출력합니다.
플로이드-워셜 알고리즘은 시간복잡도가 O(n^3)입니다. 이 문제의 경우 N이 최대 50까지 주어지기 때문에 해결이 가능합니다.
파이썬 코드
n = int(input())
friends = [list(input()) for _ in range(n)]
connected = [[0] * n for _ in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if i == j:
continue
if friends[i][j] == "Y" or (friends[i][k] == "Y" and friends[k][j] == "Y"):
connected[i][j] = 1
answer = 0
for row in connected:
answer = max(answer, sum(row))
print(answer)
Python
복사