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

C++에서 이진 행렬을 영행렬로 변환하는 최소 뒤집기 횟수 구하기 (BFS + 비트마스킹)

문제 개요

m × n 크기의 이진 행렬 mat이 주어졌다고 가정해 보겠습니다. 한 번의 연산(step)에서는 임의의 셀 하나를 선택하여 해당 셀의 비트와, 존재하는 경우 상하좌우 네 방향 인접 셀의 비트를 모두 뒤집을(flip) 수 있습니다. 이 문제의 목표는 mat를 영행렬(모든 원소가 0인 행렬)로 만드는 데 필요한 최소 연산 횟수를 구하는 것이며, 해가 존재하지 않으면 -1을 반환해야 합니다.

예를 들어 입력이 [[0,0],[0,1]]이라면 변환 과정은 다음과 같습니다.

C++에서 이진 행렬을 영행렬로 변환하는 최소 뒤집기 횟수 구하기 (BFS + 비트마스킹)

위 과정에서 총 3번의 뒤집기가 필요하므로 출력은 3이 됩니다.

접근 방법: BFS + 비트마스킹

행렬의 각 칸은 0 또는 1만 가지므로, 행렬 전체 상태를 하나의 정수(비트마스크)로 압축해 표현할 수 있습니다. (i, j) 위치의 값은 비트 자릿수 (i * m) + j에 대응시키면 됩니다. 이렇게 하면 행렬의 모든 가능한 상태를 정수 하나로 나타낼 수 있고, 셀을 뒤집는 상태 전이도 XOR 연산으로 간단하게 처리할 수 있습니다.

여기에 너비 우선 탐색(BFS)을 결합하면 시작 상태에서 영행렬(상태 0)까지의 최단 거리, 즉 최소 뒤집기 횟수를 구할 수 있습니다. BFS는 간선의 가중치가 모두 동일한 그래프에서 최단 경로를 보장하기 때문입니다.

알고리즘 단계

  1. n := 행의 개수, m := 열의 개수, x := 0으로 초기화합니다.
  2. 이중 반복문으로 모든 셀을 순회하면서 x에 (mat[i][j]를 (i * m) + j번 왼쪽 시프트한 값)을 더해 초기 상태의 비트마스크를 만듭니다.
  3. 크기가 2^(n * m)인 배열 dp를 선언하고 모든 값을 -1로 채웁니다. -1은 아직 방문하지 않은 상태를 의미합니다.
  4. dp[x] := 0으로 설정한 뒤 큐 q를 생성하고 x를 삽입합니다.
  5. q가 빌 때까지 다음을 반복합니다.
    - current := q의 맨 앞 원소를 꺼냅니다.
    - current가 0이면 dp[current]를 반환합니다. 영행렬에 도달했다는 뜻입니다.
    - 모든 셀 (i, j)에 대해 temp := current로 복사한 후, temp를 (i * m) + j번째 비트와 XOR 연산합니다(선택한 셀 뒤집기).
    - 네 방향 dir[k]에 대해 인접 좌표 (ni, nj)를 계산하고, 행렬 범위를 벗어나면 다음 반복으로 건너뜁니다. 범위 안이라면 temp를 (ni * m) + nj번째 비트와 XOR 연산합니다(인접 셀 뒤집기).
    - dp[temp]가 -1(미방문)이면 dp[temp] := dp[current] + 1로 갱신하고 temp를 큐에 삽입합니다.
  6. 큐가 소진될 때까지 영행렬에 도달하지 못하면 -1을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   int minFlips(vector<vector<int>>& mat) {
      int n = mat.size();
      int m = mat[0].size();
      int x = 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            x += (mat[i][j] << ((i * m) + j));
         }
      }
      vector < int > dp(1 << (n*m), -1);
      dp[x] = 0;
      queue <int> q;
      q.push(x);
      while(!q.empty()){
         int current = q.front();
         q.pop();
         if(current == 0)return dp[current];
         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
               int temp = current;
               temp ^= (1 << ((i *m) + j));
               for(int k = 0; k < 4; k++){
                  int ni = i + dir[k][0];
                  int nj = j + dir[k][1];
                  if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;
                  temp ^= (1 << ((ni *m) + nj));
                }
               if(dp[temp] == -1){
                  dp[temp] = dp[current] + 1;
                  q.push(temp);
                }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0},{0,1}};
   cout << (ob.minFlips(v));
}

입력

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

출력

3

복잡도 분석

가능한 행렬 상태는 최대 2^(n × m)개이고, 각 상태에서 최대 n × m개의 셀을 뒤집어 보므로 시간 복잡도는 O(2^(n·m) · n · m), 공간 복잡도는 O(2^(n·m))입니다. 따라서 이 방식은 n × m이 작은 경우(일반적으로 3×3 이하)에 실용적입니다.

마무리

이 문제는 겉보기에는 단순한 시뮬레이션처럼 보이지만, 상태 공간을 비트마스크로 압축하고 BFS로 최단 경로를 찾는 전형적인 상태 공간 탐색(state-space search) 유형입니다. 같은 패턴은 스위치 켜고 끄기 퍼즐, 슬라이딩 퍼즐 등 다양한 문제에 응용되므로 잘 익혀두면 큰 도움이 됩니다.