1704 - 붕어빵타이쿤

문제 링크

---

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

문제 요약

---

\(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("");
    }
  }
}