백준 1080 행렬(c++)

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

1080번: 행렬

이 문제는 3*3 행렬을 반대로 (0->1, 1->0) 뒤집어서 주어진 A에서 행렬 B로 만들 수 있는 최소 연산 횟수를 물어보는 문제입니다. 이 문제의 핵심은 (N-2) * (M-2)의 연산을 수행해 보는 것입니다. 왜냐하면 이 연산을 모두 수행했을 때, 주어진 행렬 B와 일치하지 않으면 더 이상 행렬 B를 만들 수 없기 때문입니다. 이러한 연산으로 인해, 어떠한 원소를 두 번 뒤집는 것은 원래대로 돌아오기 것이기에 불필요한 연산을 줄이고 뒤집는 횟수를 최소화할 수 있습니다. 연산의 횟수를 최소화해야 하는 문제이기 때문에 그리디 알고리즘으로 분류할 수 있게 됩니다.

 

<코드>

#include <cstdio>

int a[51][51];
int b[51][51];

using namespace std;

void flip(int x, int y)
{
    for (int i = x - 1; i <= x + 1; i++)
    {
        for (int j = y - 1; j <= y + 1; j++)
        {
            a[i][j] = 1 - a[i][j];
        }
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    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]);
        }
    }

    int result = 0;
    for (int i = 0; i < n - 2; i++)
    {
        for (int j = 0; j < m - 2; j++)
        {
            if (a[i][j] != b[i][j])
            {
                result += 1;
                flip(i + 1, j + 1);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] != b[i][j])
            {
                printf("-1\n");
                return 0;
            }
        }
    }

    printf("%d", result);
    return 0;
}

<참고 자료>

https://www.acmicpc.net/board/view/13509

글 읽기 - 문제 해결전략이 왜 그리디인지 모르겠습니다.