[백준/c++] 1080번: 행렬

 

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

1080번: 행렬

 

0과 1로만 이루어진 행렬 A와 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램

행렬을 변환하는 연산은 어떤 3x3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0->1, 1->0)

 

행렬 A와 B는 크기가 같으므로 이중 for문으로 함께 인덱스를 이동하면서 둘의 원소가 같은지 체크한다. 

만약 동일하지 않다면 change 함수를 호출하는데, 이 함수에는 3x3 크기로 원소를 뒤집을 수 있다.

모든 원소를 보고 난 후에, 다시 for문을 돌면서 동일하지 않은 것이 있다면 -1을 출력하고 끝내고

모두 동일하면 ans를 출력하고 끝낸다.

 

#include <iostream>
using namespace std;
#define MAX 50

char a[MAX][MAX], b[MAX][MAX];

void change(int y, int x)
{
    for (int i = y; i < y + 3; i++){
        for (int j = x; j < x + 3; j++){
            a[i][j] = a[i][j] == '1' ? '0' : '1';
        }
    }
}

int Solution(int N, int M)
{
    int answer = 0;

    for (int i = 0; i < N - 2; i++){
        for (int j = 0; j < M - 2; j++){
            if (a[i][j] != b[i][j]){
                change(i, j);
                answer++;
            }
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(a[i][j] != b[i][j])
                return -1;
        }
    }
    return answer;
}

int main()
{
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> a[i][j];
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> b[i][j];
    cout << Solution(N, M) << '\n';
    return 0;
}

 

사실 처음부터 끝까지 체크를 하면 안되지 않을까.. 싶었는데 잘 작동했다..^^