[백준] 1058.py : 친구

www.acmicpc.net/problem/1058

1058번: 친구

---

• 처음에는 각 노드별로 연결된 노드들에 대해서 set 로 저장한 다음, 자신과 연결된 친구들의 set 들을 모두 합하려고 하였는데, 알 수 없는 이유로 틀렸습니다가 떴다.
• 이산수학 시간에 배웠던 대로, 현재 문제는 2번 걸쳐서 연결된 친구를 구하는 것이기 때문에, 그래프를 만든 후 제곱해준다.
• 제곱한 그래프가 2번에 걸쳐 연결되는 그래프니까, 기존 그래프와 더할 경우 2-친구 관계 그래프가 만들어진다.
• 거기서 루프를 제외해주고, 연결 횟수는 중요하지 않으니 전부 1로 취급해준 뒤 각 행별로 더해주고 최댓값을 구해준다.

---

n = int(input())
graph = [[1 if v=='Y' else 0 for v in input()] for _ in range(n)]		# 입력받은 그래프
graph2 = [[sum(graph[i][x]*graph[x][j] for x in range(n)) for j in range(n)] for i in range(n)]  # 제곱
graph3 = [[int(bool(graph[i][j]) or bool(graph2[i][j])) if i!=j else 0 for j in range(n)] for i in range(n)]  # 2-친구
print(max([sum(graph3[i]) for i in range(n)]))