C++로 이진 행렬의 모든 요소를 1로 만드는 최소 연산 횟수 구하기

문제 개요

N행 M열로 이루어진 이진 행렬(0과 1만 포함)이 주어집니다. 이 행렬에 허용되는 연산은 임의의 인덱스 (x, y)를 선택하여, 왼쪽 상단 모서리가 (0, 0)이고 오른쪽 하단 모서리가 (x-1, y-1)인 직사각형 영역 내의 모든 요소를 뒤집는(toggle) 것입니다. 여기서 '뒤집기'란 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.

목표는 행렬의 모든 요소를 1로 만드는 데 필요한 최소 연산 횟수를 구하는 것입니다.

예시

입력 행렬:
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{1, 1, 1, 1, 1}
{1, 1, 1, 1, 1}

정답: 1

위 행렬에서 한 번의 연산으로 (3, 3)을 선택하면 왼쪽 위 영역 전체가 뒤집혀 행렬 전체가 1로 채워지게 됩니다.

접근 방법 및 알고리즘

핵심 아이디어는 행렬의 마지막 지점 (N-1, M-1)부터 시작해 역순으로 행렬을 순회하는 것입니다. 순회 중 값이 0인 셀을 만나면, 해당 셀이 속한 직사각형 영역 전체를 뒤집습니다.

뒤에서부터 탐색하기 때문에 이미 처리된 영역은 다시 확인할 필요가 없으며, 이 방식을 통해 각 0 값을 하나의 연산으로 처리할 수 있어 최소 연산 횟수를 보장할 수 있습니다.

C++ 구현 예제

#include <iostream>
#define ROWS 5
#define COLS 5
using namespace std;

int getMinOperations(bool arr[ROWS][COLS]) {
    int ans = 0;
    // 행렬을 역순으로 순회
    for (int i = ROWS - 1; i >= 0; i--) {
        for (int j = COLS - 1; j >= 0; j--) {
            // 값이 0인 셀을 발견하면 연산 횟수 증가 후 영역 전체를 뒤집음
            if (arr[i][j] == 0) {
                ans++;
                for (int k = 0; k <= i; k++) {
                    for (int h = 0; h <= j; h++) {
                        if (arr[k][h] == 1)
                            arr[k][h] = 0;
                        else
                            arr[k][h] = 1;
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    bool mat[ROWS][COLS] = {
        0, 0, 1, 1, 1,
        0, 0, 0, 1, 1,
        0, 0, 0, 1, 1,
        1, 1, 1, 1, 1,
        1, 1, 1, 1, 1
    };
    cout << "Minimum required operations = " << getMinOperations(mat) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum required operations = 3

시간 복잡도

각 0 셀을 발견할 때마다 해당 직사각형 영역을 순회하며 뒤집기 때문에 시간 복잡도는 O((N×M)²)입니다. 행렬 크기가 작은 경우에는 충분히 실용적이지만, 더 큰 입력에는 최적화된 접근이 필요할 수 있습니다.