[백준] 1080번 : 행렬 (C++)

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을 출력한다.

 

 

 

 

 

 

풀이)

 

// 1080. 행렬
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int n, m;
vector<vector<bool>> vec;
vector<vector<bool>> origin;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.resize(n, vector<bool> (m, 0));
    origin.resize(n, vector<bool>(m, 0));
 
    string temp;
    // 행렬 A 저장
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        for (int j = 0; j < m; j++)
        {
            if (temp[j] == '0') vec[i][j] = false;
            else vec[i][j] = true;
        }
    }
 
    // 행렬 B 저장
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        for (int j = 0; j < m; j++)
        {
            if (temp[j] == '0') origin[i][j] = false;
            else origin[i][j] = true;
        }
    }
 
    // 3x3 변환이 불가능한 경우
    // 두 행렬이 같은지 다른지를 체크해야 한다.
    if (n < 3 || m < 3)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (vec[i][j] != origin[i][j])
                {
                    cout << -1;
                    return 0;
                }
            }
        }
        cout << 0;
        return 0;
    }
 
 
    int ans = 0;
 
    for (int i = 0; i <= n - 3; i++)
    {
        for (int j = 0; j <= m - 3; j++)
        {
            bool flag = 0;
 
            if (vec[i][j] != origin[i][j])
            {
                flag = 1;    // vec 행렬에 변경이 있음.
                ans++;        // 변경 횟수 +
                for (int k = i; k < i + 3; k++)
                {
                    for (int l = j; l < j + 3; l++)
                    {
                        // 뒤집기
                        vec[k][l] = !vec[k][l];
                    }
                }
            }
 
            bool check = 0;
            // 변경점이 있다면 전체 배열 확인
            if (flag)
            {
                for (int k = 0; k < n; k++)
                {
                    for (int l = 0; l < m; l++)
                    {
                        if (vec[k][l] != origin[k][l])
                        {
                            // 좀 더 수정이 필요함
                            check = 1;
                            break;
                        }
                    }
                    if (check) break;
                }
            }
 
            // 두 행렬이 같다면 변경 회수 출력하고 return
            // 이번 변경으로 인해서 두 행렬의 모든 부분이 같다면.
            if (flag && !check)
            {
                cout << ans;
                return 0;
            }
        }
    }
 
    // 두 행렬은 같아질 수 없음.
    cout << -1;
    
    return 0;
}
 

---

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

1080번: 행렬