백준 1080번: 행렬

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

1080번: 행렬

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

이 문제 풀 떄 최솟값에 집중해서 어떻게 하면 최솟값이 나올까 고민했다. 그렇게 접근하니 코드 구현이 어려워지고 나 스스로 포기하게 되었다. 근데 조금만 생각해보면 굳이 최솟값은 고민 안해도 된다.

그냥 a행렬과 b행렬 원소가 일치하면 행렬 변환 안하고 일치 하지 않으면 행렬 변환 하면 된다. 여기서 중요한 것은 같이 변환 되는 3*3행렬은 신경 안써도 된다. 왜냐하면 그 행렬에 있는 원소들도 차례대로 변환 할 수 있는 기회가 올 것이다. 어차피 원소가 다르면 변환은 필수적이기 때문에 한개의 원소를 조건으로 구현해도 된다. 

 

즉 모든 원소 (i,j) (0<=i<N-2,0<=j<M-2) 에 대해서 차례대로 순회하면서 다른경우에 (i,j)~(i+2,j+2) 를 행렬변환 하면 된다.

코드를 보자

#include <cstdio>
using namespace std;
int a[50][50];
int b[50][50];
void change(int n,int m){                //3*3 타일 행렬 변환 함수
    for(int i=n;i<n+3;i++){
        for(int k=m;k<m+3;k++){
            if(a[i][k]==1){
                a[i][k]=0;
            }
            else if(a[i][k]==0){
                a[i][k]=1;
            }
        }
    }
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){            //a행렬 입력
        for(int k=0;k<m;k++){
            scanf("%1d",&a[i][k]);
        }
    }
    for(int i=0;i<n;i++){            //b행렬 입력
        for(int k=0;k<m;k++){
            scanf("%1d",&b[i][k]);
        }
    }
    int ans =0;
    for(int i=0;i<n-2;i++){
        for(int k=0;k<m-2;k++){
            if(a[i][k]!=b[i][k]){      //원소 (0,0)부터 a행렬이랑 b핼렬이 다르면 행렬 변환 
                ans++;
                change(i,k);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int k=0;k<m;k++){
            if(a[i][k]!=b[i][k]){        //a행렬 b행렬이 일치하지 않으면 -1
                ans=-1;
                break;
            }
        }
    }
    printf("%d",ans);

}