\(N*M\)크기의 격자판이 주어진다. 이 격자판에는 0또는 1이 적혀져 있는데 \((x, y)\)를 누르면 \((x, y)\)를 포함 상, 하, 좌, 우 이렇게 다섯개 칸의 상태가 토글된다. 최소한의 연산 횟수를 통해 격자판의 모든 수를 0으로 만드는것이 목표다. 최소한의 연산 횟수를 가지는 것이 여러개라면 사전순으로 빠른 답을 출력한다.
문제 풀이
상태가 토글된다는 것이 이 문제를 푸는 핵심이다. \((x, y)\)를 누르면 해당 칸과 주위 네 방향이 같이 토글된다. 이 때 동일한 칸을 두 번 이상 누를 필요가 없다. 왜냐하면 두번 이상 누르는 순간 기존의 상태와 똑같아 지거나 한번 누른 상태와 똑같아 지기 때문이다. 그렇다면 \((x, y)\)를 언제 눌러야 할까? 여기서 우리는 이 문제를 \(greedy\)로 접근을 할 수 있다. 왼쪽 맨 위칸부터 오른쪽으로 봐 가면서 만약 상태가 1이라면 바로 아래칸을 눌러서 0으로 만들어 주는 전략을 사용한다. 즉 순서를 강제시켜주는 것이다.
이것이 과연 올바른 정답을 낼 수 있을까? 불행히도 아니다. 맨 윗칸은 종속되는 상태가 없고 맨 윗칸에서 어떻게 누르냐에 따라 정답이 달라지기 때문이다. 그렇다면 우리는 맨 윗칸의 상태를 고정해 주면 된다. 다행이 \(M\)의 크기는 최대 15밖에 안되고 맨 윗줄의 상태는 최대 \(2^{15}\)밖에 안되기 때문이다. 따라서 우리는 맨 윗칸의 상태를 고정시켜 두고 해당 경우에 대해 \(greedy\)하게 접근을 해 주면 된다.
총 시간복잡도는 \(O(N*M*2^M)\)이다.
소스 코드
#include <stdio.h>
#include <string.h>
const int INF = 987654321;
const int dx[] = {0, -1, 0, 1, 0};
const int dy[] = {0, 0, -1, 0, 1};
int row, col, A[20][20], B[20][20], C[20][20], ans[20][20];
bool isRange(int x, int y) {
if (x == -1 || x == row || y == -1 || y == col) {
return false;
}
return true;
}
void toggle(int x, int y) {
for (int i = 0 ; i < 5 ; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (isRange(nx, ny)) {
B[nx][ny] ^= 1;
}
}
}
int func(int topState) {
int ret = 0;
memcpy(B, A, sizeof(A));
memset(C, 0, sizeof(C));
for (int i = 0 ; i < col ; ++i) {
if (topState & (1 << i)) {
++ret;
C[0][i] = 1;
toggle(0, i);
}
}
for (int i = 1 ; i < row ; ++i) {
for (int j = 0 ; j < col ; ++j) {
if (B[i - 1][j]) {
++ret;
C[i][j] = 1;
toggle(i, j);
}
}
}
for (int i = 0 ; i < row ; ++i) {
for (int j = 0 ; j < col ; ++j) {
if (B[i][j]) {
return INF;
}
}
}
return ret;
}
int main() {
scanf("%d%d", &row, &col);
for (int i = 0 ; i < row ; ++i) {
for (int j = 0 ; j < col ; ++j) {
scanf("%d", &A[i][j]);
}
}
int mmin = INF;
for (int i = 0 ; i < (1 << col) ; ++i) {
int ret = func(i);
if (ret < mmin) {
mmin = ret;
memcpy(ans, C, sizeof(C));
}
}
if (mmin == INF) {
puts("IMPOSSIBLE");
} else {
for (int i = 0 ; i < row ; ++i) {
for (int j = 0 ; j < col ; ++j) {
printf("%d ", ans[i][j]);
}
puts("");
}
}
}