BOJ 1080:: 행렬

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

 

종만북 초반에 나오는 Lights Out 퍼즐(https://en.wikipedia.org/wiki/Lights_Out_(game)https://www.acmicpc.net/problem/14927)과 매우 유사한 문제입니다.

다만 난이도 자체는 더 쉽네요.

일단 3×3 부분 행렬에 대해 연산한다는 말이 어려우니까, 그냥 행렬의 어떤 칸을 선택하면 그 칸을 중심으로 하는 3×3 영역이 반전된다고 합시다.

중요 아이디어는

  1. 동일한 칸을 두 번 이상 선택할 필요가 없습니다. 어차피 짝수 번 선택하면 선택 안 한 것과 똑같으므로 선택할지 말지만 결정하면 됩니다.
  2. 선택 순서는 중요하지 않습니다. 3행 2열을 선택한 다음 5행 7열을 선택한 것과 그 반대 순서로 선택한 결과가 똑같습니다.
따라서 순서 생각하지 말고 2행 2열부터 $n-1$행 $m-1$열까지 (1행이나 $n$행, 1열, $m$열은 선택 불가. 왜 그런진 아시죠?) 차례대로 2중 반복문 돌면서 선택할지 말지 결정합시다.
예를 들어, $A$와 $B$가 다음과 같다고 합시다.
먼저 2행 2열(파란색)의 선택 여부를 정해야 합니다. 여기서 왼쪽 위에 있는 1행 1열(빨간색)을 보면 $A$와 $B$에서 다릅니다. 앞으로 지나갈 2행 3열, 2행 4열, 3행 2열… 등은 선택하더라도 1행 1열의 값을 바꾸진 못하기 때문에 지금 2행 2열을 선택해서 $A$의 1행 1열을 0으로 만들지 않으면 영영 같게 만들 기회를 놓치게 됩니다. 그러므로 2행 2열은 무조건 선택해야 하는 칸입니다.
선택 후엔 아래 그림처럼 됩니다. 그 다음 2행 3열로 넘어갑시다. 왼쪽 위 1행 2열을 보면 $A$와 $B$에서 서로 같죠. 2행 3열을 선택해버리면 1행 2열의 값이 달라져버릴 것이고 그걸 다시는 원래대로 되돌릴 수 없기 때문에 2행 3열은 선택하면 안 됩니다.
이런 식으로 선택 가능한 6개 칸에 대해 선택 여부를 다 결정해주면 됩니다. 이 예제에서는 총 4칸을 선택하면 되고, 선택 후 $A$와 $B$가 동일하기 때문에 답은 4가 됩니다. 만약 이 알고리즘으로 선택해야 할 칸을 골라서 그것들을 다 선택했는데도 $A$와 $B$가 다르면 그냥 $A$를 $B$로 바꾸는 게 불가능한 경우입니다.
P.S. Lights Out은 여기에다 브루트 포스로 탐색 좀 섞어놓은 문제입니다.
#include<cstdio>
 
 
using namespace std;
 
int n, m;
char a[50][51], b[50][51];
 
 
void toggle(int i, int j) {
    for (int ii = i-1; ii <= i+1; ii++)
        for (int jj = j-1; jj <= j+1; jj++)
            a[ii][jj] = '0' + '1' - a[ii][jj];
}
 
 
bool check_same(void) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] != b[i][j])
                return false;
    return true;
}
 
 
int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", a[i]);
    for (int i = 0; i < n; i++)
        scanf("%s", b[i]);
        
    int cnt = 0;
    for (int i = 1; i < n-1; i++)
        for (int j = 1; j < m-1; j++)
            if (a[i-1][j-1] != b[i-1][j-1]) {
                toggle(i, j);
                cnt++;
            }
                
    printf("%d", check_same()? cnt : -1);
    
    return 0;
}