[Greedy] 백준 1080번 - 행렬

그리디.. 어렵고 어렵다 

난 일단 문제 읽고 뭔 소리지 싶었다.. 문제부터 막혔다

 

 

 

일단 3 X 3 연산에 대해 생각해보았다

 

총 (M-3) X (N-3)의 연산이 이루어진다는 것인데...!

매번 연산 하나 할때 마다 행렬 B와 비교해서 최소를 찾는다?

문제점. 어디부분을 연산부터 해야 최소 횟수를 찾을 수 있는것인가

              순서대로 하면 최소값 못찾을 거 같고 심지어 B 행렬로 만들어 낼 수 있음에도 못 만들 가능성도 있다

 

그렇다면????

 

A 와 B가 다른 부분만 inverse 연산 해주면 된다! 

그럼 다른 A와 B가 다른 부분을 표시하는 임시 행렬 tmp를 만들어준다

그럼 이제 tmp 행렬에서 1인 부분만 파악을 해서 그 부분을 기준 삼아 3x3 연산을 실행해 주면 된다

 

CASE 0 ) 행렬이 같은 경우

사전에 tmp 행렬을 제작할 때 1의 개수를 카운트하여 같은 경우를 조기에 잡아내자

 

CASE 1 ) 행렬 N<3 M<3인 경우

N,M이 3보다 작은 경우 연산 자체가 불가하므로 -1 뱉어주어야 한다

 

 

CASE 2 ) 행렬 N>=3 M>=3 인 경우

행렬 tmp에서 1인 부분만 골라서 3x3연산 돌린다

하지만 될성 부른 나무는 떡잎부터 알아볼 수 있는 방법이 있다

 

> 조기 진단하고 -1 때려버리는 방법

 

0<= x <= M-3 / 0<= y <= N-3 이기 때문에!

아래의 세가지 조건에 걸린다면 바로 중단하고 -1을 때려버리면 된다

 

주의할 것!

  세가지 종류의 조기진단 방법은 모두 거쳐야 한다

 

세가지 조건에 안 걸린다면 매번 3 x 3연산의 개수를 세어주고 끝까지 가면 된다

 

코드

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

int N, M, total, diff;
char input;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;

    int arrA[N][M];
    int arrB[N][M];
    int tmp[N][M];

    //arrA에 값 입력
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> input;
            arrA[i][k] = input - 48;
        }
    }

    //arrB에 값 입력 동시에 arrA와 비교 후 tmp에 값 입력
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> input; //int로 입력받으면 M자리수의 정수가 들어가므로 char로 입력 받아 한글자씩 입력한다
            arrB[i][k] = input - 48; //char을 int로 변환
            if (arrA[i][k] == arrB[i][k])
                tmp[i][k] = 0;
            else{
                tmp[i][k] = 1;
                diff++;
            }
        }
    }
    if(diff == 0){
        cout<<0<<endl;
        return 0;
    }

    if (N < 3 || M < 3)
    {
        cout<<-1<<endl;
        return 0;
    }

    for (int i = 0; i < N - 2; i++)
    {
        for (int k = 0; k < M - 2; k++)
        {
            if (i == N - 3) //미리 가능성이 안 보이는 케이스는 싹을 잘라버리기 위해 0이든 1이든 다 N-3에서 검사 한다 
            {
                if (tmp[i + 1][k] != tmp[i][k] || tmp[i + 2][k] != tmp[i][k])
                {
                    cout << -1 << endl;
                    return 0;
                }
            }
            
            if (k == M - 3) //미리 가능성이 안 보이는 케이스는 싹을 잘라버리기 위해 0이든 1이든 다 M-3에서 검사 한다 
            {
                if (tmp[i][k + 1] != tmp[i][k] || tmp[i][k + 2] != tmp[i][k])
                {
                    cout << -1 << endl;
                    return 0;
                }
            }

            if (i == N - 3 && k == M - 3) //미리 가능성이 안 보이는 케이스는 싹을 잘라버리기 위해 0이든 1이든 다 N-3 / M-3 에서 검사 한다 
            {
                if (tmp[i + 1][k + 1] != tmp[i][k] || tmp[i + 1][k + 2] != tmp[i][k] || tmp[i + 2][k + 1] != tmp[i][k] || tmp[i + 2][k + 2] != tmp[i][k])
                {
                    cout << -1 << endl;
                    return 0;
                }
            }
            if (tmp[i][k] == 1) //arr A와 arr B가 다른 부분인 경우
            {

                //3*3 inverse 연산
                for (int l = 0; l < 3; l++)
                {
                    for (int m = 0; m < 3; m++)
                    {
                        tmp[i + l][k + m] = 1 - tmp[i + l][k + m];
                    }
                }
              
                total++;
            }
        }
    }


    cout << total << endl;
    return 0;
}

 

 

문제 링크 

www.acmicpc.net/problem/1080

1080번: 행렬