[leetcode][1277] Count Square Submatrices with All Ones

문제 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/

---

1과 0으로 이루어진 N x M 배열이 주어지면 1로 이루어진 정사각형의 개수를 구하라.

---

행, 열 subsum을 구한 뒤 이를 이용하여 구했다.

입력배열이 위와 같으면 행, 열 부분합 배열은 각각 위와같이 만들어진다.

(2,1) 한 칸이 정사각형인지 판단하는 방법은 행 부분합에서 (2, 1) - (1,1) 값과 열 부분합에서 (2,1) - (2,0) 값이 둘 다 1이어야 한다. 즉, (2,1) 값이 1인지 확인하기만 하면 된다. 

그 다음 (2,1)을 정사각형의 왼쪽 모서리로 두고 사이즈가 2인 정사각형이 가능한지 판단해보자.

이전 단계에서 (2, 1)은 모두 1인 것을 판별했다. 따라서 (2, 2), (3, 1), (3, 2)가 모두 1인지만 확인한다면 사이즈가 2인 정사각형이라고 볼 수 있다. (2, 2), (3, 2)이 1인지는 행 부분합, (3, 1), (3, 2)는 열 부분합으로 구할 수 있다. 

즉, 행 부분합에서 (3, 2) - (1, 2)를 뺀다면 이는 (2, 2), (3, 2) 값들의 합이 되고 따라서 이 값이 2가 되어야 한다.(배열은 0 아니면 1만 나올 수 있기 때문) 열 부분합도 이와 마찬가지로 (3, 2) - (3, 0)을 뺐을 때 값이 2가 된다면 (2, 2), (3, 2)가 둘다 1이라고 볼 수 있다.

(1,1)을 정사각형의 왼쪽 모서리로 두고 사이즈가 2인 정사각형이 될 수 있는지 판단해보자.

열 부분집합에서 (2,2) - (2,0)은 2가 되지만 행 부분집합에서 (2,2)- (0,2)가 1이 되기 때문에 모든 칸이 1이 되지 않아 이는 정사각형이 되지 못한다고 볼 수 있다.

 

위 방법으로 정사각형의 왼쪽 모서리를 정하는 2중 for 문과 size를 정하는 for문을 한 번 돌리면서(즉, 3중 for문) 정사각형의 개수를 구한다.

 

시간복잡도는 왼쪽 모서리를 정하는데 O(NM), size를 정하는데 대충.. O(min(N, M))정도(더 상세히는 등차수열) 걸린다. 따라서 대~략 O(NM * min(N,M)). 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1277.%20Count%20Square%20Submatrices%20with%20All%20Ones.cpp