백준 12024번, 사각형 찾기 풀이

문제

백준 12024번

풀이

DFS로 짜면 TLE가 나니 다른 방법을 고려해야 합니다.   

$ i $, $ j $가 정해져있고, $ k_{1} $과 $ k_{2} $가 $ i $와 $ j $를 제외한 서로 다른 임의의 정점이라고 두겠습니다.   
$ i \to k_{1} $, $ k_{1} \to j $ 로 가는 방법이 있다고 하면  $ i $에서 $ j $로 가는 경로가 있다는 말과 같습니다.  
반대로, $ j \to i $로 가는 간선도 있어야 합니다.   
$ j \to k_{2} $, $ k_{2} \to i $ 를 통해서 가는 방법이 있다면, 이 역시 $ j $에서 $ i $로 가는 경로가 있다는 말과 같습니다.  

$ i \to j \to i $로 가는 과정이 한가지 경우의 수가 됩니다.   



또한, 문제에서 양방향(무방향) 그래프라고 주어졌기 때문에, 임의의 정점 $ k $에 대해서 $ i \to k \to j $가 있으면, $ j \to k \to i $도 있습니다.   
같은 길로 돌아오는 경우($ i \to j $와 $ j \to i $의 과정에서 $ k $가 같은 경우)를 제외한 모든 경로의 수가 답이므로, $ i \to j $ (혹은 $ j \to i $)로 가는 경우의 수가 $ n $이라고 하면 모든 경로의 수는 $ _{n}P_{2} $ 이 되겠네요.   

모든 $ i $, $ j $에 대해서, 모든 $ k $에 방문해야하니 시간 복잡도는 $ O(N^3) $이 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int graph[251][251];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			int a;
			cin >> a;
			if (a) graph[i][j] = 1;
		}

	long long ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			long long cnt = 0;
			for (int k = 1; k <= n; k++) {
				if (i == j || j == k || i == k) continue;
				if (graph[i][k] && graph[j][k]) cnt++;
			}
			ans += cnt * (cnt - 1);
		}

	cout << ans;
}