[BOJ 12024 // C++] 사각형 찾기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 12024번 문제인 사각형 찾기이다.
문제는 아래 링크를 확인하자.

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

12024번: 사각형 찾기

문제에서 주어지는 인접행렬(adjacency matrix)을 거듭제곱하면 두 노드 사이의 거리 2인 경로의 수를 얻을 수 있다.

 

위의 성질을 이용해 문제를 해결하자.

 

답이 int 범위를 넘을 수 있음에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;

int arr[250][250];
int arr2[250][250];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> arr[r][c];
	}

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			for (int k = 0; k < N; k++) arr2[r][c] += arr[r][k] * arr[k][c];
		}
	}
	
	ll ans = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (r == c) continue;
			ans += arr2[r][c] * (arr2[r][c] - 1);
		}
	}

	cout << ans;
}