2차원 동전 뒤집기

직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.

제한사항
1 ≤ beginning의 길이 = target의 길이 ≤ 10
1 ≤ beginning[i]의 길이 = target[i]의 길이 ≤ 10
beginning[i][j]와 target[i][j]는 i + 1행 j + 1열의 동전의 상태를 나타내며, 0 또는 1의 값으로 주어집니다.
0은 동전의 앞면을, 1은 동전의 뒷면을 의미합니다.

문제를 보고 생각한것.

완전탐색문제인가? 가능은 한거같은데 범위가 배열의 값보다는 크지않다.
결국 행부터 뒤집나 열부터 뒤집나 상관없음 DFS로 가능해보인다.
그런데 0,1만 존재하면 비트마스킹이 DFS보다 낫지않을까?
비트마스킹으로 열의 대한 값을 잡고 행은 뒤집을 필요가 있을때만(모든 행이 target의 행과 다를때) 뒤집는 방식으로 문제풀이가 가능해보인다.

class Solution {
    public int solution(int[][] beginning, int[][] target) {
        int n = beginning.length;
        int m = beginning[0].length;
        int [][] map  = new int[n][m];
        int answer = Integer.MAX_VALUE;
        //비트 마스킹
        for(int i=0;i < 2 << m;i++){
            int tmp = 0;
             
            // 초기 값이 계속필요하므로 초기값 지정
            arrayCopy(map,beginning);
            
            // col값
            for(int j=0;j<m;j++){
                if((i & 2 << j )== 0 ) continue;
                tmp++;
                flip(map,j);
            }
            //row값
            boolean flag = false;
            
            for(int j=0;j<n;j++){
                //이미 앞행에 값이 다르므로 break;
                if(flag) break;
                // row값 비교를 위한 if문 
                if(map[j][0]==target[j][0]){
                    for(int k=1;k<m;k++){
                        
                        if(map[j][k]!=target[j][k]){
                            flag = true;
                            break;
                        }
                    }
                }else{
                    for(int k=1;k<m;k++){
                        if(map[j][k]==target[j][k]){
                            flag =  true;
                            break;
                        }
                    }
                    if(!flag) tmp++;
                }
                
               
            }
            //비교문
            if(!flag) answer = Math.min(answer,tmp);
        }
        if(answer==Integer.MAX_VALUE) return -1;
        return answer;
    }
    
    void arrayCopy(int[][] map,int[][] begin){
         for(int i=0;i<begin.length;i++){           
            System.arraycopy(begin[i], 0, map[i], 0, begin[0].length);        
        }
    }
    void flip(int[][] map,int j){
        for(int i=0;i<map.length;i++){
            map[i][j] = map[i][j]== 0 ? 1 : 0 ;
        }
    }
}//비트 마스킹을 이용한 문제풀이