[C++] BAEKJOON 1080 행렬

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

1080번: 행렬

그리디 알고리즘 을 사용하여 문제를 해결하였습니다.

세로에 대해서는 세로길이-2 까지, 가로에 대해서는 가로길이-2 까지 순회를 하며 행렬을 뒤집을지 말지 결정해주었습니다. (0,0) 부분에 대해서 영향을 미치는 경우는 좌측 상단 모서리에 위치한 3*3 부분 행렬을 뒤집을 때 뿐이고 이 연산을 수행한 후, (0,1) 부분에 영향을 미치는 경우는 (0,1) 부터 시작하는 3*3 부분 행렬을 뒤집을 때 뿐입니다. 때문에 세로길이-2,가로길이-2 까지 순회하며 뒤집을지 말지 결정해주면 최소연산으로 가능한지 확인할 수 있습니다.

#include <iostream>

using namespace std;

int a[50][50], b[50][50];

void matrixChange(int n,int m){
    for (int i=n;i<=n+2;i++){
        for (int j=m;j<=m+2;j++){
            a[i][j] = 1 - a[i][j];
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int N,M;
    cin >> N >> M;
    
    int count = 0;
    
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            scanf("%1d", &a[i][j]);
        }
    }
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            scanf("%1d", &b[i][j]);
        }
    }
    
    for (int i=0;i<N-2;i++){
        for (int j=0;j<M-2;j++){
            if (a[i][j] != b[i][j]){
                matrixChange(i,j);
                count++;
            }
        }
    }
    
    int flag = 0;
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            if (a[i][j] != b[i][j]){
                count = -1;
                flag = 1;
                break;
            }
        }
        if (flag) break;
    }
    
    cout << count << "\n";
    
    return 0;
}