[백준] #1080 행렬 - (BF)

문제

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

1080번: 행렬

목적

2개의 행렬 A, B가 주어졌을때 A를 변환하여 B로 만들때의 최소 변환횟수 구하기

+ 행렬의 변환은 변환위치를 기준으로 3*3만큼의 부분행렬을 변환함.

 

풀이

이 문제는 내가 제대로 이해를 못한거같다.

일단 변환은 3*3의 부분행렬만 변환하는것이므로 행렬의 원소를 오른쪽위에서 왼쪽아래로 하나하나 비교하면서 다르면 변환을 진행하되 범위에 제한을 N-3, M-3으로 줘야지 3*3행렬의 변환을 진행할수있다.

그리고 일단 오른쪽위부터 시작해서 내려오므로 가장 오른쪽위인 원소 즉, 기준점은 한번 변환된다면 다음에는 변환될 일이 없으므로 그리디하게 진행함.

 

코드

#include <iostream>

using namespace std;

int N, M;
bool origin[51][51];
bool target[51][51];

//두개의 행렬을 같은지 비교함
bool isSame() {
    for (int i=0; i<N; ++i) {
        for (int j=0; j<M; ++j) {
            if (origin[i][j] != target[i][j])
                return false;
        }
    }
    return true;
}
//기준점으로부터 3*3만큼의 부분행렬을 변환
void convert(int ip, int jp) {
    for (int i=ip; i<ip+3; ++i) {
        for (int j=jp; j<jp+3; ++j) {
            if (origin[i][j])
                origin[i][j] = 0;
            else
                origin[i][j] = 1;
        }
    }
}
//기본 변환함수
//원소를 하나하나 오른쪽위에서부터 아래로 비교해나감
//변환후에는 같은지 확인
int change() {
    int cnt = 0;
    for (int i=0; i<N-2; ++i) {
        for (int j=0; j<M-2; ++j) {
            if (origin[i][j] != target[i][j]) {
                cnt++;
                convert(i, j);
            }
            if (isSame())
                return cnt;
        }
    }
    return -1;
}
int main() {
    cin >> N >> M;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<M; ++j) {
            scanf("%1d", &origin[i][j]);
        }
    }
    for (int i=0; i<N; ++i) {
        for (int j=0; j<M; ++j) {
            scanf("%1d", &target[i][j]);

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

    cout << change();
}