백준 / 1080 / 행렬 / C++

문제 링크 : https://www.acmicpc.net/problem/1080

#include <bits/stdc++.h>

using namespace std;

int anscount = 0;

void change(vector<vector<int>> &arr, int startx, int starty)
{
    for(int i = startx; i < startx + 3; i++)
    {
        for(int j = starty; j < starty + 3; j++)
        {
            if(arr[i][j] == 0)
            {
                arr[i][j] = 1;
            }
            else
            {
                arr[i][j] = 0;
            }
        }
    }
    anscount++;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n,m;
    cin >> n >> m;
    vector<vector<int>> arr(n,vector<int>(m));
    vector<vector<int>> ans(n,vector<int>(m));
    for(int i = 0; i < n; i++)
    {
        string tmp;
        cin >> tmp;
        for(int j = 0; j < m; j++)
        {
            arr[i][j] = tmp[j] - '0';
        }
    }
    for(int i = 0; i < n; i++)
    {
        string tmp;
        cin >> tmp;
        for(int j = 0; j < m; j++)
        {
            ans[i][j] = tmp[j] - '0';
        }
    }
    if(n < 3 || m < 3)
    {
        if(arr != ans)
        {
            cout << -1;
        }
    else
        {
            cout << anscount;
        }
        return 0;
    }
    for(int i = 0; i <= n - 3; i++)
    {
        for(int j = 0; j <= m - 3; j++)
        {
            if(arr[i][j] != ans[i][j])
            {
                change(arr,i,j);
            }
        }
    }
    if(arr != ans)
    {
        cout << -1;
    }
    else
    {
        cout << anscount;
    }
}

문제에서 정의한 행렬 변환 연산은 $3 \times 3$ 범위에 있는 값을 0 -> 1, 1 -> 0으로 바꾸는 연산이다.

문제를 풀기 위해서는 $3 \times 3$이라는 범위에 주목해봐야 하는데, 우선 9개 칸 중 맨 왼쪽 위 칸을 기준 칸(비교하는 칸)이라고 설정한 후에 행렬 A의 값을 비교해 나간다. 기준 칸을 기존 행렬의 0,0부터 차례로 비교해 나가는데, 이 때 기준 칸의 값이 비교 행렬 값과 다르다면 변환 연산을 해준다. 물론 범위는 $3 \times 3$이 적용된다.

이렇게 쭉 비교와 변환을 이어나가다 보면 행렬의 끝쪽 모서리 값보다 2 작은 칸(마지막 변환된 칸)에서 마지막 비교를 하게 되는데, 남은 마지막 칸 전 칸과 마지막 칸은 변환 연산을 하지 않는다. 왜냐하면 그 칸에 변환 연산을 적용한다면 이미 확정지어 둔 마지막 변환된 칸이 다시 0이면 1, 1이면 0으로 되돌아오기 때문에 변환 연산을 하는 의미가 없고, 이 칸에 대해 변환 연산을 적용해야 한다면 이미 출력값은 -1로 확정된다.

이렇게 0 ~ N-2 / 0 ~ M-2의 탐색을 모두 마친 후에 원래 행렬과 비교한 후 행렬이 같다면 변환한 횟수를, 다르다면 -1을 출력해 주면 된다.