[1080번] 행렬

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

2. 그리디 알고리즘

이 문제가 왜 그리디인지 생각해보자.

0행 0열의 값이 1이고 결과로 원하는 값에서는 0이었다면 0행 0열의 값은 무조건 0,0번째에서 밖에 뒤집지 못한다.

따라서 우리는 0,0부터 n-1, m-1까지 뒤집기를 쭉 진행하여 최소 횟수를 구할 수 있게 된다.

즉, 0행 0열의 값이 1인데 원하는 값에서는 0이라면 0,0이 아닌 다른 위치에서는 저 값을 뒤집지 못한다는 것과 동치이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
bool arr[52][52];
bool ans[52][52];
 
int n, m;
bool flip(int a, int b)
{
    if (a + 3 > n || b + 3 > m)
        return false;
 
    for (int i = a; i < a + 3; i++)
        for (int j = b; j < b + 3; j++)
            arr[i][j] = !arr[i][j];
 
    return true;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%1d", &arr[i][j]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%1d", &ans[i][j]);
    
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr[i][j] != ans[i][j]) // 서로 값이 다르다면
            {
                if (flip(i, j)) // 뒤집기마다 시도 횟수 + 1
                    cnt++;
                else // 뒤집을 수 없다면 -1
                {
                    printf("-1");
                    return 0;
                }
            }
 
    printf("%d", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>