C++로 이진 행렬에서 네 모서리가 모두 1인 직사각형 찾기

이진 행렬(binary matrix)이 주어졌을 때, 네 개의 모서리가 모두 1인 직사각형이 존재하는지 확인하는 문제입니다. 예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.

이 행렬의 경우 결과는 "예"입니다. 실제로 아래와 같이 네 모서리가 모두 1인 직사각형이 하나 존재합니다.

접근 방법

모든 경우를 무작정 검사하는 브루트 포스 방식보다, 해시 기반 자료구조를 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 행렬을 위에서 아래로 한 행(row)씩 차례대로 훑습니다.

• 각 행에서 값이 1인 두 열의 조합(열 인덱스 쌍)을 해시 셋(hash set)에 저장해 둡니다.

• 이후 행에서 동일한 열 조합이 다시 발견되면, 해당 두 열과 두 행이 이루는 사각형의 네 모서리가 모두 1이라는 의미이므로 곧바로 직사각형의 존재를 확인할 수 있습니다.

C++ 구현 예제

#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<vector>
using namespace std;
bool isRectanglePresent(const vector<vector<int> >& matrix) {
   int rows = matrix.size();
   if (rows == 0)
   return false;
   int columns = matrix[0].size();
   unordered_map<int, unordered_set<int> > table;
   for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < columns - 1; ++j) {
         for (int k = j + 1; k < columns; ++k) {
            if (matrix[i][j] == 1 && matrix[i][k] == 1) {
               if (table.find(j) != table.end() && table[j].find(k) != table[j].end())
                  return true;
               if (table.find(k) != table.end() && table[k].find(j) != table[k].end())
                  return true;
               table[j].insert(k);
               table[k].insert(j);
            }
         }
      }
   }
   return false;
}
int main() {
   vector<vector<int> > matrix = {
      { 1, 0, 0, 1, 0 },
      { 0, 0, 1, 0, 1 },
      { 0, 0, 0, 1, 0 },
      { 1, 0, 1, 0, 1 }
   };
   if (isRectanglePresent(matrix))
      cout << "Rectangle is present";
   else
      cout << "Rectangle is not present";
}

출력

Rectangle is present

복잡도 분석

시간 복잡도: 각 행마다 가능한 모든 열 쌍을 검사하므로 O(R × C²)입니다. 여기서 R은 행의 수, C는 열의 수입니다.
공간 복잡도: 해시 맵에 저장해야 하는 열 쌍의 최대 개수에 비례하므로 O(C²)입니다.

이처럼 해시 셋에 이미 등장한 열 조합을 기록해 두면, 중복 조합이 나타나는 순간 즉시 직사각형 여부를 판별할 수 있어 불필요한 반복 탐색을 크게 줄일 수 있습니다.