[cpp 알고리즘] 백준 1080 행렬

[백준] 1080 행렬 풀이

알고리즘: 그리디 알고리즘

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

문제 요약

- N*M 크기의 행렬이 두 개 주어진다.

- 기존 A의 행렬을 B로 바꾸는데 필요한 연산 횟수의 최소값을 구하면 된다. (연산은 모든 원소를 뒤집는 것을 의미한다.)

풀이 정리

- 두 행렬의 요소들을 각각 비교하고 동일하면 0, 다르다면 1로 구성된 temp 배열을 만들었다.

- (0,0)부터 (N,M)까지 확인해보면서 서로 다르다면(=1이라면) 그 부분을 기준으로 3*3 만큼 모든 원소를 뒤집었다. 

C++ 코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;

int arr[55][55];
int arr2[55][55];
int temp[55][55]; //차이를 저장하는 배열

void changeMatrix(int y, int x){
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(temp[y+i][x+j] == 1) {
                temp[y+i][x+j] = 0;
            }
            else if (temp[y+i][x+j] == 0) {
                temp[y+i][x+j] = 1;
            }
        }
    }
}

int main(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            char c; cin >> c;
            arr[i][j] = c-'0';
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            char c; cin >> c;
            arr2[i][j] = c-'0';
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(arr[i][j] == arr2[i][j]) temp[i][j]=0;
            else temp[i][j]=1;
        }
    }
    
    int ans=0;
   
    for(int i=0; i<=N-3; i++){
        for(int j=0; j<=M-3; j++){
            if(temp[i][j] == 1){ // 위에서부터 1 만나면 바꾸기
                changeMatrix(i, j);
                ans++;
            }
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(temp[i][j] == 1) {
                cout << -1 << "\n";
                return 0;
            }
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

60%에서 틀렸습니다

처음에는 예제3을 보고 3이하의 수를 아래와 같이 처리해 주었다.

하지만 3*3이하의 수 이지만, 이미 행렬이 같다고 주어진 경우가 있을수도 있으므로 이 코드를 없애 주었다.

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