[Baekjoon] 행렬

👀 문제 설명

문제

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

3 4

0000

0010

0000

1001

1011

1001

 

예제 출력 1

2

 

✍🏻풀이

(0, 0)부터 (N - 3, M - 3)의 범위까지의 두 행렬을 비교한다. 

각 위치에서 두 행렬의 값이 다르면 0 -> 1, 1-> 0으로 바꿔주는 연산을 한다. (이 때, answer += 1)

해당 범위에서의 비교 + 연산을 끝낸 후, 

다시 두 행렬을 비교해서 만약 다른 값이 있다면 -1을 출력해준다.

 

코드

//
//  BOJ_1080.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/11/26.
//  Copyright © 2020 조수민. All rights reserved.
//
//  행렬(https://www.acmicpc.net/problem/1080)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<vector<int>> matrixA, matrixB;
int answer = 0;
int N, M;

void change(int y, int x) {
    for (int i = y; i < y + 3; i++) {
        for (int j = x; j < x + 3; j++) {
            matrixA.at(i).at(j) = 1 - matrixA.at(i).at(j);
        }
    }
}

void input() {
    // input
    cin >> N >> M;
    
    matrixA.resize(N);
    matrixB.resize(N);
    for (int i = 0; i < N; i++) {
        matrixA.at(i).resize(M);
        matrixB.at(i).resize(M);
    }
    
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        
        for (int j = 0; j < M; j++) {
            matrixA.at(i).at(j) = str[j] - '0'; // char 데이터형을 int형을 변환하는 간단한 방법 (숫자가 아스키 코드라는 것을 활용)
        }
    }
    
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        
        for (int j = 0; j < M; j++) {
            matrixB.at(i).at(j) = str[j] - '0';
        }
    }
}

int main() {
    input();
    
    // 3 * 3 행렬로 바뀌므로 i와 j는 각각 N - 3, M - 3까지
    for (int i = 0; i < N - 2; i++) {
        for (int j = 0; j < M - 2; j++) {
            if (matrixA.at(i).at(j) != matrixB.at(i).at(j)) { // 다르면 연산을 해준다.
                answer++;
                change(i, j);
            }
        }
    }
    
    // 연산 이후
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (matrixA.at(i).at(j) != matrixB.at(i).at(j)) { // 다른 값이 나왔다면 연산을 아무리 해도 같아질 수 없으므로 -1을 출력
                cout << -1;
                return 0;
            }
        }
    }
    
    cout << answer;
    
    return 0;
}