백준 1080번 C++ 풀이

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

1080번: 행렬

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	실버 1

문제

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

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

입력

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

출력

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

---

이 문제의 핵심은 어디서 연산을 수행할 것인지를 알아내는게 이 문제의 핵심이다. 다음의 행렬이 있다고 가정하자.

 

1	0	1	0	0
0	0	0	0	1
1	0	0	1	1
0	1	1	1	0
0	0	0	0	0

 

이 행렬의 좌상단을 (0, 0)이라고 하고, 우하단을 (4, 4)라고 하자. (비교할 대상은 없지만) 이 행렬에서 어디에서 연산을 수행하는 것이 최적인지 알아내려면, 정말 많고 복잡한 과정을 통해 알아내야 할 것이다. 하지만 조금 다르게 생각해보자. (2, 1)에서 연산을 수행한 후에, (0, 1)에서 연산을 수행한 것과, (0, 1)에서 연산을 수행한 후, (2, 1)에서 연산을 수행한 행렬이 과연 같을까 다를까? 당연히 같다. 이를 통해 알 수 있는 것은, 이 연산은 교환 법칙이 성립한다. (a, b)에서 연산을 수행하고나서 (c, d)에서 연산을 하는 것과, (c, d)에서 연산을 수행하고 (a, b)에서 연산을 수행하는 것은 같은 결과를 내놓는다는 것이다. 

 

이를 통해 우리는 최적의 위치를 찾은 후에 연산을 수행할 필요없이, 그냥 맨 처음부터 연산을 실행하는 것은 결과적으로 동일한 풀이인 셈이다.

 

그러면 어디서, 무슨 기준으로 연산을 수행해야 하는가? 를 해결해야 한다. 간단하다. 이 연산에 관한 것을 무시하고 그냥 한칸에 대해서 0이면 1로, 1이면 0으로 연산한다고 생각해보자. 당신이라면 어떨때 연산을 하겠는가? 당연히 비교하는 행렬과 그 위치의 숫자가 다르면 연산을 수행할 것이다. 이 아이디어를 그대로 가져오면 된다.

 

#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;

void change(vs& v, int x, int y) {
    for(int i = y; i < y + 3; i++) {
        for (int j = x; j < x + 3; j++) {
            v[i][j] = v[i][j] == '1' ? '0' : '1';
        }
    }
}

bool same(const vs& input, const vs& target, int x, int y) {
    for(int i = 0; i < y; i++) {
        if (input[i] != target[i]) return false;
    }
    return true;
}

int main () {
    // fast i/o
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int x, y; // 행렬의 크기
    int cnt = 0; // 연산 횟수
    string temp; // 행렬 입력을 위한 
    vs input, target;

    cin >> y >> x;

    input.resize(y); target.resize(y); // 미리 할당

    for(auto& v : input) cin >> v;
    for(auto& v : target) cin >> v;

    /*
     * 어디서부터 연산을 수행하던 이 연산은 교환법칙이 성립하기 때문에, 
       최적의 위치를 찾고 찾아 연산하는 것은 결국 맨 처음위치부터 연산을 수행하는 것과 같다.     
     * 또한 같은 위치에서의 중복연산은 최소값이 되지 않을 뿐더러, 최소값이 되어야 한다고 해도, 하나마나인 행동이다.
     * 현 위치로부터 3 x 3안의 구역에서 연산하기 때문에 0 ~ x - 3, 0 ~ y - 3의 범위만을 탐색한다.
    */
    for(int i = 0; i < y - 2; i++) {
        for(int j = 0; j < x - 2; j++) {
            if (input[i][j] != target[i][j]){
                cnt++;
                change(input, j, i);
            }
        }
    }
    cout << (same(input, target, x, y) ? cnt : -1);
}