2차원 동전 뒤집기

• 문제 링크

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

• 푼 방법

이 문제의 핵심은 이미 뒤집은 열 혹은 행은 다시 뒤집지 않아도 된다는 것이다.

1. 이미 뒤집은 열 혹은 행은 다시 뒤집지 않아도 된다.
2. 그렇기 때문에 행을 뒤집는 경우의 수인 2 ^ H, 열을 뒤집는 경우의 수인 2 ^ W 의 경우의 수를 곱한 경우의 수가 존재한다. ex) H = 10, W = 10 총 경우의 수 = 2 ^ 20
3. 위와 같이 가정을 세웠다면, 그냥 모든 경우의 수를 진행해주면 된다.
4. 위를 행하기 위해서 비트 연산을 실행
5. 예를 들어 H = 2, W = 3 일 때, 총 5자리로 표현할 수 있고, 이 경우 비트가 10/101 이면, 첫번째 행을 뒤집고, 첫번째 열, 세번째 열을 뒤집는 것이다. (00000 ~ 11111, 0 ~ 31, 2 ^ H * 2 ^ W)
6. 위와 같이 가정을 세워놓고 진행하면 구현은 간단하게 할 수 있다.

• 시간 복잡도

O((2 ^ H) * (2 ^ W) * H * W)

• Code

import java.util.*;

class Solution {
    
    public int H;
    public int W;
    public int[][] b;
    public int[][] t;

    public int parsing(int number) { // 비트를 파싱하는 메서드 
        int count = 0; // 뒤집은 횟수를 기록
        int[][] c = new int[H][W]; // beggining 을 복사한 배열
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                c[i][j] = b[i][j];
            }
        } // 복사
        
        for (int i = 0; (1 << i) <= number; i++) {
            if ((number & (1 << i)) != 0) { // 뒤집어야 하는 경우
                count++; // 뒤집은 횟수를 기록
                change(c, i); // 실제로 뒤집는 행위
            }
        }
        
        if (equal(c)) { // 뒤집은 결과가 target 과 동일한지 검증
            return count; // 동일하다면 뒤집은 횟수를 반환
        }
        
        return Integer.MAX_VALUE; // 해당 비트로는 동일한 결과를 만들 수 없다면 invalid 한 값 반환
    }
    
    public void change(int[][] c, int digit) {
        if (digit < H) { // digit 이 H 보다 작다면 행을 뒤집는다
            changeRow(c, digit);
        } else { // digit 이 H 보다 크거나 같다면 열을 뒤집는다.
            changeCol(c, digit - H);
        }
    }
    
    public boolean equal(int[][] c) { // 두개의 배열이 같은지 비교하는 연산
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (c[i][j] != t[i][j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    public void changeRow(int[][] c, int row) { // 행을 뒤집는 연산
        for (int i = 0; i < W; i++) {
            c[row][i] = (c[row][i] + 1) % 2;
        }
    }
    
    public void changeCol(int[][] c, int col) { // 열을 뒤집는 연산
        for (int i = 0; i < H; i++) {
            c[i][col] = (c[i][col] + 1) % 2;
        }
    }
    
    public int solution(int[][] beginning, int[][] target) {
        this.H = beginning.length;
        this.W = beginning[0].length;
        this.b = beginning;
        this.t = target;
        
        int total = (int) Math.pow(2, H) * (int) Math.pow(2, W); // 전체 경우의 수를 구함
        int answer = Integer.MAX_VALUE;
        
        for (int i = 0; i < total; i++) {
            answer = Math.min(answer, parsing(i)); // parsing 하면서 가장 작은 값 골라냄
        }
       
        return answer == Integer.MAX_VALUE ? -1 : answer; // 맞추지 못하는 경우 -1 반환
    }
}