Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 행렬을 모두 0으로 만드는 최소 연산 횟수 구하기

문제 소개

이진 행렬(binary matrix)이 하나 주어져 있다고 가정해 보겠습니다. 여기서 말하는 '연산'이란 행렬의 한 칸(셀)을 선택했을 때, 그 셀 자신과 상·하·좌·우에 인접한 셀들을 한 번에 뒤집는(0 ↔ 1) 작업을 의미합니다. 우리가 구해야 할 것은 이런 연산을 반복하여 행렬의 모든 원소를 0으로 만들기 위한 최소 연산 횟수이며, 아무리 연산해도 모든 원소를 0으로 만들 수 없다면 -1을 반환해야 합니다.

예를 들어 입력 행렬이 다음과 같다고 합시다.

00
10

이 경우 필요한 최소 연산 횟수는 3입니다.

C++로 이진 행렬을 모두 0으로 만드는 최소 연산 횟수 구하기

접근 방법: 비트마스크 + 너비 우선 탐색(BFS)

행렬의 각 칸은 0 또는 1 두 가지 상태만 가지므로, 행렬 전체의 상태를 하나의 비트마스크(bitmask) 정수로 압축해 표현할 수 있습니다. 예를 들어 r×c 크기의 행렬이라면 (i, j) 위치의 값을 비트 위치 i*c + j에 대응시키면 됩니다. 이렇게 하면 복잡한 행렬 상태를 정수 하나로 다룰 수 있고, 셀을 뒤집는 연산 역시 XOR 비트 연산으로 간단히 처리할 수 있습니다.

목표가 '최소' 연산 횟수이므로, 초기 상태에서 출발해 가능한 모든 상태를 너비 우선 탐색(BFS)으로 확장하면서 각 상태에 도달하기까지의 최소 거리를 기록하면 됩니다. 모든 원소가 0인 상태(비트마스크 값 0)에 도달했을 때의 거리가 곧 정답이며, 끝내 도달하지 못한다면 -1이 그대로 반환됩니다.

알고리즘 단계

  • 4방향 이동 배열 dir을 정의합니다: {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
  • getPos(i, j): 2차원 좌표를 1차원 비트 위치(i * c + j)로 변환하는 함수
  • getCoord(x): 1차원 비트 위치를 다시 2차원 좌표(x / c, x % c)로 변환하는 함수
  • 메인 로직은 다음과 같이 진행됩니다:
    • r, c에 행렬의 행·열 크기를 저장하고 last = r * c로 설정
    • 입력 행렬을 순회하며 초기 상태 mask를 생성 (matrix[i][j] 값을 getPos(i, j)번째 비트에 반영)
    • 크기 512(= 2⁹)의 dist 배열을 -1로 초기화 → 최대 3×3 크기의 행렬까지 지원
    • 큐에 초기 mask를 넣고 dist[mask] = 0으로 설정한 뒤 BFS 시작
    • 큐가 빌 때까지 반복:
      • 현재 상태 mask를 큐에서 꺼냄
      • 모든 칸 i에 대해, 해당 칸과 인접 칸들을 XOR로 뒤집은 새 상태 nmask를 계산 (범위를 벗어나는 이웃은 건너뜀)
      • nmask를 아직 방문하지 않았거나(dist[nmask] == -1), 더 짧은 경로로 도달할 수 있으면 dist[nmask]를 갱신하고 큐에 삽입
    • 탐색이 끝나면 dist[0], 즉 전부 0인 상태까지의 최소 거리를 반환

아래 예제 코드를 통해 더 잘 이해해 보겠습니다.

예제

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c;
int r;
int last;
const int inf = 1e6;

int getPos(int i, int j){
    return i * c + j;
}
pair<int, int> getCoord(int x){
    pair<int, int> ret;
    ret.first = x / c;
    ret.second = x % c;
    return ret;
}

int solve(vector<vector<int>>& matrix) {
    int mask = 0;
    r = matrix.size();
    c = r ? matrix[0].size() : 0;
    last = r * c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            mask ^= (matrix[i][j] << getPos(i, j));
        }
    }
    vector<int> dist(1 << 9, -1);
    queue<int> q;
    q.push(mask);
    dist[mask] = 0;
    while(!q.empty()){
        mask = q.front();
        q.pop();

        for(int i = 0; i < last; i++){
            pair<int, int> coord = getCoord(i);
            int x = coord.first;
            int y = coord.second;

            int nmask = mask;
            nmask ^= (1 << i);
            for(int k = 0; k < 4; k++){
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];
                if(nx < 0 || nx >= r || ny < 0 || ny >= c)
                    continue;
                int pos = getPos(nx, ny);
                nmask ^= (1 << pos);
            }

            if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){
                dist[nmask] = dist[mask] + 1;
                q.push(nmask);
            }
        }
    }
    return dist[0];
}
int main(){
    vector<vector<int>> v = {{0, 0},{1, 0}};
    cout << solve(v);
}

입력

{{0, 0},{1, 0}}

출력

3

복잡도 분석

행렬의 상태 수는 최대 2^(r·c)개이고, 각 상태마다 r·c개의 칸에 대해 연산을 시도하므로 시간 복잡도는 O(2^(r·c) × r × c)입니다. 방문 여부와 거리를 저장하는 dist 배열 때문에 공간 복잡도는 O(2^(r·c))입니다. 이처럼 상태 공간 탐색 기반 접근은 행렬의 크기가 작을 때 매우 효과적이며, BFS의 성질 덕분에 목표 상태에 도달하는 경로가 항상 최소 연산 횟수임을 보장할 수 있습니다.