사각형 세기
면접 대비시간 제한2초메모리 제한128 MB
N이 최대 250인 무향 그래프의 인접 행렬이 주어질 때 시작점과 방향이 다른 경우를 구분하여 길이가 4인 사이클 개수를 구합니다.
문제
무방향 그래프가 주어진다. 이 그래프에 들어 있는 사각형의 개수를 세어라.
사각형은 서로 다른 네 정점으로 이루어진 길이 4인 사이클이다. 정점 가 모두 다르고 , , , 이 모두 간선이면 이 순서가 사각형 하나가 된다.
정점을 방문하는 순서가 다르면 다른 사각형으로 센다. 예를 들어 1 -> 2 -> 3 -> 4 -> 1과 2 -> 3 -> 4 -> 1 -> 2는 따로 센다.
입력
첫째 줄에 정점의 개수 이 주어진다. ()
다음 개의 줄에는 무방향 그래프의 인접행렬 가 주어진다. 각 줄에는 0 또는 1인 정수가 개씩 공백으로 구분되어 들어 있다. 정점 와 정점 를 잇는 간선이 있으면 가 1이고, 없으면 0이다. 가 1인 경우는 없다.
출력
사각형의 개수를 한 줄에 출력한다.