백준 1080. 행렬

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

1080번: 행렬

 

코드 자체는 금방 구성했는데 문제를 잘못 생각해서 예외처리 때문에 상당히 애먹었다.

문제에 n,m은 50미만 자연수라고 했으므로 n,m은 3미만일수도 있다.

그래서 예를들어 input이 다음과 같이 주어지면 

 

2 2

00

11

11

00

 

한번 뒤집어서 A를 B로 만들수 있을것으로 생각하고 풀었는데 아무리 해도 틀렸습니다가 나왔다.

하다하다 안되서 질문검색에서 보니 이런 경우에는 뒤집을수 없고 -1을 출력하는 것이였다..

 

문제를 풀때 최대한 답을 안보려고 하는 편인데 이럴때마다 그냥 막히면 보는것이 맞나 싶다.

시간이 너무 소요된다 ㅜ

 

---

문제는 그리디 알고리즘 문제로서 A와 B를 (0,0)부터 비교해가면 서로 다르다면 3x3을 뒤집는것을 반복해서 A가 B가 되는지 판단하는 문제이다.

뒤집고 난 후에 이전에 뒤집은 것에 대하여 생각할 필요는 없다.

어처피 숫자는 0 or 1 이고, A와 B가 다른 부분이 있어서 뒤집었기 때문에 다시 뒤집게 된다면 그 부분이 무조건 차이가 나게된다.

 

#include <iostream>

using namespace std;

int n,m;

char A[55][55];
char B[55][55];

// 3x3 뒤집기
void Flip(int r, int c)
{
    for(int i = r; i < r+3; i++)
    {
        for(int j = c; j < c+3; j++)
        {
            if(A[i][j] == '0')
                A[i][j] = '1';
            else
                A[i][j] = '0';
        }
    }
}

// A와 B가 같은가
bool IsItSame()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(A[i][j] != B[i][j]) return false;
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        scanf("%s", &A[i]);
    }
    for(int i = 0; i < n; i++)
    {
        scanf("%s", &B[i]);
    }

    int cnt = 0;
    for(int i = 0; i <= n-3; i++)
    {
        for(int j = 0; j <= m-3; j++)
        {
            // 다르다면 (i,j)로부터 3x3 뒤집어본다
            if(A[i][j] != B[i][j])
            {
                cnt++;
                Flip(i,j);
            }
        }
    }

    if(IsItSame())
    {
        cout << cnt;
        return 0;
    }
    else
    {
        cout << -1;
        return 0;
    }
}