[BOJ 1080] 행렬(C++)

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

1080번: 행렬

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

 

 

 

A 행렬을 B 행렬로 만든다는 것은, 값이 다른 행렬의 원소들을 모두 바꿔야하는 것을 의미한다.

 

 

 

 

이중 For문을 이용해 순차적으로 값이 다른 행렬의 원소들을 바꾸면서 정답을 찾을 수 있을까?

 

 

 

 

값이 다른 원소들을 임의의 순서로 골라서 바꿔야지 연산 횟수의 최솟값을 찾지 않을까?

 

 

 

 

위의 질문에 대해서 답을 할 수 있으면, 이 문제를 확실하게 풀 수 있다.

 

 

 

 

임의의 순서로 골라서 값을 바꾸면, 일부의 경우에 연산 횟수의 최솟값이 나타나지 않을 수도 있다. 왜냐하면, 이중포문을 이용해서 순차적으로 값을 찾는 것은, 이전의 바뀌어진 원소들에 대해서 최소의 영향을 주게 된다.

 

 

 

 

반대로, 임의의 순서로 바꾸게 되면 기존의 원소들에 영향을 주므로 연산의 최솟값을 찾을 수 없는 경우도 있다.

 

 

 

 

해설코드(C++).

#include <iostream>
using namespace std;
 
int N, M;
 
char A[51][51];
int answer = 0;
bool chk[51][51] = {false};
 
int main() {
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> A[i][j];
        }
    }
    
    char c;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> c;
            if(c != A[i][j])
                chk[i][j] = true;
        }
    }
    
    for(int i = 0; i < N - 2; i++){
        for(int j = 0; j < M - 2; j++){
            if(chk[i][j]){
                answer += 1;
                for(int k = 0; k < 3; k++){
                    for(int m = 0; m < 3; m++){
                        if(chk[i + k][j + m] == true)
                            chk[i + k][j + m] = false;
                        else
                            chk[i + k][j + m] = true;
                    }
                }
            }
        }
    }
    
    for(int i = 0; i < N ; i++){
        for(int j = 0; j < M; j++){
            if(chk[i][j]){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    
    cout << answer << endl;
    return 0;
}