[23058] 뒤집기 게임

https://www.acmicpc.net/problem/23058

23058번: 뒤집기 게임

<문제>

하나의 행과 열을 두번이상 뒤집는 경우는 애초에 정답의 가능성이 없으므로 배제,

1번 뒤집는거나 3번뒤집는게 결과가 똑같고, 0번뒤집나 2번뒤집나 결과가 같다면

횟수를 최소화할것이므로 결국 뒤집거나 안뒤집거나이다.

행이나 열을 선택해서 뒤집는 경우에 대해 브루트포스를 적용하여, (1<<17)-1개의 경우의 수를 만들어준다.

하나의 경우의 수에 대해서, 0과 1중 많은쪽으로 1개씩 뒤집는다고 생각하면 된다. 이 부분은 그리디를 적용한 셈이다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int a[9][9], clone[9][9];
int n, cnt;
void toggleX(int y) {
    cnt++;
    for (int i = 0; i < n; i++) a[y][i] = 1 - a[y][i];
}
void toggleY(int x) {
    cnt++;
    for (int i = 0; i < n; i++) a[i][x] = 1 - a[i][x];
}
int main(void) {
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            cin >> a[i][j];
            clone[i][j] = a[i][j];
        }
    const int BIT = (1 << (n + 1)) - 1;
    int ans = 54321;
    for (int bty = 0; bty < BIT; bty++) {
        for (int btx = 0; btx < BIT; btx++) {
            for (i = 0; i < n; i++)
                for (j = 0; j < n; j++) a[i][j] = clone[i][j];
            cnt = 0;
            for (i = 0; i < n; i++)
                if (bty & (1 << i)) toggleY(i);
            for (i = 0; i < n; i++)
                if (btx & (1 << i)) toggleX(i);
            int c1 = 0, c2 = 0;
            for (i = 0; i < n; i++)
                for (j = 0; j < n; j++) {
                    c1 += (a[i][j] == 1);
                    c2 += (a[i][j] == 0);
                }
            cnt += min(c1, c2);
            ans = min(cnt, ans);
        }
    }
    cout << ans;
    return 0;
}