[BOJ] 1080 : 행렬 C++

문제

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

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

 

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

 

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

예제 입력 1	예제 출력 1
3 4 0000 0010 0000 1001 1011 1001	2

 

 

CODE

#include <bits/stdc++.h>

using namespace std;

int N, M;
int matrixA[50][50];
int matrixB[50][50];

void toggle(int r, int c) // (i, j)가 가장 왼쪽 위의 원소인 3 X 3 크기의 부분행렬 뒤집기
{
    for(int i = r; i < r + 3; i++)
    {
        for(int j = c; j < c + 3; j++)
        {
            matrixA[i][j] ^= 1;
        }
    }
}

void solve()
{
    int answer = 0;
    for(int i = 0; i < N - 2; i++)
    {
        for(int j = 0; j < M - 2; j++)
        {
            if(matrixA[i][j] != matrixB[i][j]) // (0, 0) ~ (N-2, M-2) 원소 하나씩 비교
            {
                toggle(i, j);
                answer += 1;
            }
        }
    }

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(matrixA[i][j] != matrixB[i][j]) // A를 B로 바꿀 수 없을 경우 
            {
                answer = -1;
            }
        }
    }
    cout << answer;
}

int main()
{
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%1d", &matrixA[i][j]);
        }
    }
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%1d", &matrixB[i][j]);
        }
    }
    solve();
}

 

COMMENT

 N X M 행렬을 입력받은 뒤 (N-2) X (M-2) 부분행렬만을 차례로 비교하여 뒤집은 후 두 행렬이 같아지면 뒤집은 횟수를, 같아지지 않는다면 -1을 출력하면 되는 문제이다. 여기서 왜 차례로 한번씩만 비교하면 되는가를 생각해 볼 필요가 있는데, 그 이유는 다음과 같다.

 

 (i, j)가 가장 왼쪽 위의 원소인 3 X 3 부분행렬을 뒤집는 것을 toggle(i, j)라 하자.

   1. 어떤 부분행렬부터 뒤집는가, 즉 부분행렬을 뒤집는 순서는 결과에 영향이 없다.

   2. (0, 0)을 뒤집을 수 있는 방법은 toggle(0, 0)뿐이다.

     - 이후 A의 (0, 1)과 B의 (0, 1)이 다르다면 동일하게 만드는 방법은 toggle(0, 1)뿐이다.

       (toggle(0, 0)을 한다면 원소 (0,0)이 달라질 수 있다.) 

     - 계속해서, A의 (N-2, M-2)와 B의 (N-2, M-2)이 다르다면 동일하게 만드는 방법 또한 toggle(N-2, M-2)뿐이다.

   3. (0, 0) ~ (N-2, M-2)를 동일하게 만들었다고 가정하자.

     - toggle(i, j)를 두번 하는 행위는 의미가 없으므로 이전까지 뒤집은 횟수가 최솟값이다.

     - 행렬 A와 B의 원소 (N-1, M-1) ~ (N, M)중 서로 다른 원소가 있다면 답을 정할 수 없는데, 3 X 3 행렬 전체를 뒤집어야 하므로 만약 이 원소 중 하나를 뒤집고싶다면 이전에 동일하게 만든 원소중 하나 이상을 뒤집어야 하기 때문이다.

 

 앞에서 부터 차근차근 살펴보는 유형의 그리디 알고리즘 문제이다. 이런 유형의 문제는 앞에서부터 차례로 해보니 맞다 정도로 넘어가기 쉽상인데, 왜 그리디 알고리즘을 적용해도 되는 문제인가를 검증해 보는 것이 더 중요하다고 생각한다.

 

도움이 되셨다면 공감 꾸욱! 부탁드립니다 ~~!!😊