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

해당문제는 이 블로그를 참고하여 문제를 풀었습니다.

이 문제의 핵심은 바로 행과 열을 뒤집는 순서가 상관 없다는 것이다.

여기서 2행 -> 4행 -> 2열을 뒤집나
4행 -> 2행 -> 2열을 뒤집나
2열 -> 4행 -> 2행을 뒤집나
최종 그림은 똑같이 나온다.

그럼 행을 두번 뒤집는 경우도 동일할까? 그렇다.
000 111 -> 101 -> 010
111 => 111 2열뒤집기 111 다시1행 뒤집기 101

그러면 1행을 먼저 두번 뒤집은 상태인 초기상태에서 2열을 뒤집어도 동일한 상태임을 확인 할 수있다.

그러면 이 지식을 가지면 우리는 이것을 알 수 있다.

1,2,3,,,,10행에서 조합을 통해 어떤 행을 뒤집을 지 찾는다. -> 1행 뒤집기 , 1과3행을 뒤집기,, 전부 뒤집기 이런식으로

그다음에 행을 전부 뒤집었다면 열을 비교해서 target과 열이 다르다면 열을 무조건 뒤집는다. 그러고 나서 Target과 동일한지 비교하면된다.

여기서 행이 만약 5개라면 총 경우의 수는 2^5이 된다.
여기서 비트 마스크를 사용할것이다.

5행이 있다면, 비트마스크를 통해 00000, 00001, 00010,,,,11111
을통해 1이면 뒤집는 행으로 판단하면된다.

for(int rowMask =0;rowMask<(1<<n);rowMask++){
        vector<vector<int>>tmp = beginning;
        int flip=0;
        for(int i=0;i<n;i++){
            if(rowMask & (1<<i)){
                rowflip(tmp,i);
                flip++;
            }
            
        }
}

전형적인 비트마스크 코드다.
rowMask가 일단 0인건알겠고 (1<<n)이 뭔지 봐보자 1<<n에서 n이 3이면 1000이 된다. 그러면 십진수로 8이되는것이다.
그러면 rowMask가 0부터 8까지 int가 들어가는것이다.
핵심 1. n은 자리수이다. ____ n이 4이면 4자리

그렇다면 두번째 for문은 무엇일까.
rowMask가 만약 1010 이라면 2번째와 4번째 행을 뒤집어야한다.
for(int부터 n까지)자리수가들어가게되고 & 연산을 통해 2번째와 4번째가 동일한 i가 2,4일때만 참이된다. 즉 for문은 1인 자리수를 호출하는것이다.

#include <string>
#include <vector>

using namespace std;
int n=0;
int m=0;

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) {
    int answer = 0;
    
    n=beginning.size();
    m=beginning[0].size();
    
    int minFlip=999999;
    for(int rowMask =0;rowMask<(1<<n);rowMask++){
        vector<vector<int>>tmp = beginning;
        int flip=0;
        for(int i=0;i<n;i++){
            if(rowMask & (1<<i)){
                rowflip(tmp,i);
                flip++;
            }
            
        }
        
        for(int i=0;i<m;i++){
            if(tmp[0][i] != target[0][i]){
                colflip(tmp,i);
                flip++;
            }
            
        }
        
        if(tmp == target && minFlip>flip) minFlip = flip;
    }
    
    if(minFlip == 999999) {
        answer = -1;
    }else{
        answer = minFlip;
    }
    
    return answer;
}