문제

nxm 으로 되어있는 그래프가 앞면 또는 뒷면으로 존재할때
특정 타겟 그래프로 만들기위해 최소 몇번의 뒤집기가 필요한가?

단 뒤집기는 한줄을 모두 뒤집어야함.

(1번 그림에서 2,4 행을 뒤집으면 2번 그림이 되고
2번 그림에서 2,4,5번 열을 뒤집으면 3번 그림이 된다.)

풀이

먼저 알아야 할것이
몇번째 행과 열을 뒤집느냐가 안뒤집느냐가 중요하지
어떤 순서로 뒤집느냐는 중요지 않다.

예를 들어 2,4,5 열을 뒤집을때 4,2,5 5,2,4 2,5,4 등 순서는 상관없이 결과는 동일하다.
그 이유는 뒤집는다는게 0->1 , 1->0 으로 만드는건데
뒤집는 횟수를 모두 쌓아두고 한번에 뒤집어도 결과가 동일하기 떄문이다.

또한 같은 행이나 열을 2번 뒤집으면 안뒤집는것과 동일하므로 1번씩만 뒤집으면 된다.

---

그렇다면 문제가 단순해졌다.

n 행 m 열 중에서 어떤 행과 열을 골랐을때 타겟 그래프가 되느냐는것이다.
ex) 1,2,5 행과 2,3,5 열을 뒤집으면 타겟 그래프가 된다.

---

즉 n개 중 a개 선택 m개 중 b 개를 선택해야한다.

이를 쉽게 풀어쓰면
안뒤집는것 = 0, 뒤집는것 = 1 로 하고 n=5일때
00000 ~ 11111 의 경우의 수를 모두 시도해보면 된다.

n, m이 각각 10이하 이므로
2^10 x 2^10 = 2^20 = 10^6 의 경우의 수가 나온다.

결국 내가 해야할것은
0000000000,0000000000 ~ 1111111111,1111111111
까지 시도하면 된다.

(한 시도는 한 행과 열을 뒤집는 것이므로 최대 10번만 하면되므로
반복횟수는 10^7 이 나온다. 시간복잡도는 2^(2n)xn = n x 2^2n 이다.)

그럼 2가지 가지를 n+m개까지 하면되므로 bfs를 생각해볼수 있다.
하지만 나는 비트 연산으로 좀더 쉽게 구현해봤다.

비트연산

자주 쓰는 방법중 하나인데 순서가 있는 n개를임의로 선택하는 방법은
2^n이다. (고르고 안고르고 2x2x...x2 를 n개 해야하므로)

이걸 쉽게 하는 방법은 다음과 같이하면 된다.

// 1<<n은 2^n이다.
for(int bi=0;bi<(1<<n);bi++) {
	// bi는 0001100 처럼 각 자리와 비교하기위해 쓴다.
    for(int i=0;i<n;i++){
    	// 이때 각 i번째 자리를 비교해 1이 있으면 실행
    	// 0이면 패스하면 된다.
        int bi_i=1<<i;
        // and 연산을 통해 i번째 자리가 1인지 확인한다.
        if((bi&bi_i)!=0){
        	// 이때 실행!
        }
    }
}

이는 가지가 2개뿐인 dfs를 완전탐색하는것과 동일하다.
(즉 가지가 3개 이상이면 dfs를 써야한다.)

확실히 dfs 보다 코드가 짧고 프로세스가 stack을 사용하지않아
메모리적으로 효율적이다.
(단 익숙하지 않으면 실제로 쓰기가 까다로웠다.
그래서 같은 문제를 푼 다른 코드를 보니 대부분 dfs로 풀었다.)

해당 문제에서는 n x m의 모든 조합을 해봐야하므로
처음부터 n+m의 경우라고 생각하고 앞 n개는 행, 뒤 m개는 열로 생각하고 처리했다.

code

class Solution {
    int n,m;
    public int solution(int[][] origins, int[][] target) {
        // n,m
        n=origins.length;
        m=origins[0].length;
        int k=1<<(n+m);
        int ans = 21;
        int[][] graph=new int[n][m];
        for(int bi=0;bi<k;bi++){
            // copy origins
            for(int y=0;y<n;y++) for(int x=0;x<m;x++) graph[y][x]=origins[y][x];
            int moveCnt=0;
            // 앞 n 개는 행
            for(int i=0;i<n;i++){
                int bi_i=1<<i;
                // 뒤집기
                if((bi&bi_i)!=0){
                    moveCnt++;
                    move(true,i,0,graph);
                }
            }
            // 뒤 m 개는 열
            for(int j=0;j<m;j++){
                int bi_j=1<<j+n;
                if((bi&bi_j)!=0){
                    moveCnt++;
                    move(false,0,j,graph);
                }
            }
            // check
            if(isOk(graph,target)) ans=Math.min(ans,moveCnt);
        }
        if(ans==21) ans=-1;
        return ans;
    }
    void move(boolean isRow,int y,int x,int[][] graph){
        if(isRow) for(int j=0;j<m;j++) graph[y][j]=graph[y][j]==1?0:1;
        else for(int i=0;i<n;i++) graph[i][x]=graph[i][x]==1?0:1;
    }
    boolean isOk(int[][] graph,int[][] target){
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(graph[i][j]!=target[i][j]) return false;
        return true;
    }
}