[프로그래머스] 2차원 동전 뒤집기 [C++]

https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

 

 

문제 분석

2차원 배열에서 행 또는 열을 뒤집어, 목표 상태로 만들기 위한 최소 횟수를 구하는 문제이다.

각 동전은 앞면 혹은 뒷면 두가지 상태를 가지며, 한번 뒤집기를 할 때, 하나의 행 혹은 열 전채를 뒤집게 된다.

문제 접근

BFS 접근법과 그 한계

처음에는 BFS(너비 우선 탐색)를 사용하여 모든 가능한 상태를 탐색하는 것을 고려해볼 수 있다. BFS는 모든 가능한 상태를 단계별로 탐색하므로, 이론적으로는 최소 뒤집기 횟수를 찾을 수 있다.

하지만 이 방법의 시간 복잡도를 분석해 보면:

• n x m 행렬에서, 각 행과 열은 독립적으로 뒤집을 수 있다.
• 총 n + m개의 행과 열이 있으며, 각각은 뒤집거나 뒤집지 않는 두 가지 상태를 가진다.
• 따라서 총 가능한 상태의 수는 2^(n+m)
• 각 상태에서 행렬을 확인하는 데 O(n*m)

결과적으로 BFS의 시간 복잡도는 O(2^(n+m) * n * m)이 된다. 이는 매우 큰 복잡도로, 행렬의 크기가 조금만 커져도 실행 시간이 매우 증가.

• 비트마스킹을 사용한다면,
  • 각 행과 열의 뒤집기 상태를 비트로 표시할 수 있다.
  • 행이 n 개라면, 가능한 행 뒤집기 조합은 2^n 개이다.
  • 이 접근 방식을 사용하면 시간 복잡도를 O(2^n * n * m) 까지 줄일 수 있다.

비트마스킹

for (int rowMask = 0; rowMask < (1 << n); ++rowMask)

n 이 행의 수를 나타낼때, 모든 행의 뒤집기 상태를 나타내기 위한 반복문이다. (1 << n) 은 2^n 과 동일하며, 이는 곧 n개의 행에 대해 각각 뒤집을 수 있는 모든 경우의 수를 나타낸다.

예를 들어 n = 3 이라고 가정해 본다면, rowMask 는 0 ~ 7의 값을 가지게 된다.

즉, 000, 001, 010, 011, 100, 101, 110, 111 로 나타내며, 이후

if(rowMask & (1 << i))

rowMask의 i번째 비트를 확인하여 몇번째 행을 뒤집을지 결정한다

• rowMask = 0: 모든 비트가 0이므로, 아무 행도 뒤집지 않음.
• rowMask = 1: 첫 번째 비트가 1이므로, 첫 번째 행만 뒤집음.
• rowMask = 2: 두 번째 비트가 1이므로, 두 번째 행만 뒤집음.
• rowMask = 3: 첫 번째, 두 번째 비트가 1이므로, 첫 번째와 두 번째 행을 뒤집음.
• rowMask = 4: 세 번째 비트가 1이므로, 세 번째 행만 뒤집음.

위 과정을 모두 돌게 되면, 모든 행 조합에 대한 뒤집기 조합을 진행하게 된다.

이후 열의 뒤집기 조합을 고려할 때는, 비트마스킹 연산이 필요하지 않다.

열의 상태는 첫번째 행의 상태에 의해 결정되기 때문이다. 즉, 한 번 행을 뒤집고 나면, 그에 따라 열을 뒤집을지 말지가 결정되는 것이다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;

void rowFlip(vector<vector<int>>& matrix, int row){
    for(int i = 0; i < m; i++){
        matrix[row][i] = 1 - matrix[row][i];  
    }
}

void colFlip(vector<vector<int>>& matrix, int col){
    for(int i = 0; i < n; i++){
        matrix[i][col] = 1 - matrix[i][col];  
    }
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {

    n = beginning.size();
    m = beginning[0].size();

    int minFlip = -1;

    // 행의 뒤집기 상태를 나타내는 비트마스크 rowMask를 0부터 2^n까지 반복 (각 행의 뒤집기 상태를 나타냄)
    for(int rowMask = 0; rowMask < (1 << n); rowMask++) {

        vector<vector<int>> tmp = beginning;
        int flip = 0;  

        // 각 행을 뒤집을지 여부를 결정 (rowMask의 각 비트가 행을 뒤집을지 나타냄)
        for(int i = 0; i < n; i++) {
            if(rowMask & (1 << i)) {  // i번째 비트가 1이면 해당 행을 뒤집음
                rowFlip(tmp, i);      
                flip++;               
            }
        }

        // 첫 번째 행의 상태를 기준으로 열을 뒤집는 작업 수행
        for(int i = 0; i < m; i++) {
            if(tmp[0][i] != target[0][i]) {  // 첫 번째 행의 i번째 열 값이 목표 상태와 다르면
                colFlip(tmp, i);             
                flip++;                      
            }
        }

        
        if(minFlip == -1 || minFlip > flip) {  
            if(target == tmp) {                
                minFlip = flip;                
            }
        }
    }
    
    return minFlip;
}