[BOJ] 1080: 행렬

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

BOJ - 1080: 행렬

문제 유형 : 행렬, 그리디, 비트마스크

문제 난이도 : Silver I

 

문제

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

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

 

입력

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

 

출력

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

 

풀이

이 문제는 그리디로 풀 수 있다. 

우선, 행렬은 하나만 만들어서 A행을 우선 저장한 뒤, B행의 값을 xor시키면 된다. 두 행렬의 비트차가 중요하니까, 이 정보면 충분하다.

이제 이 행렬을 모두 0으로 만들면 된다.

좌측 상단부터 우측 하단순으로 행우선으로 각 칸을 확인하면서, 칸이 1이면 그 칸을 왼쪽 맨 위로 하여 3 * 3의 크기를 비트 플립하면 된다.

다 끝나고도 아직 1이 남아있다면, 불가능하므로 -1을 출력하고, 아니라면 비트플립 횟수를 출력하면 된다.

 

코드

C++

#include <iostream>
#include <vector>

using namespace std;

int n, m;

void flip(int row, int col, vector<vector<int>>& mat) {
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 3; ++j) {
      mat[row + i][col + j] ^= 1;
    }
  }
}

bool isFinished(vector<vector<int>>& mat) {
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) {
      if(mat[i][j]) return false;
    }
  }
  return true;
}

int main() {
  cin >> n >> m;

  vector<vector<int>> mat(n, vector<int>(m));

  string temp;
  for(int i = 0; i < n; ++i) {
    cin >> temp;
    for(int j = 0; j < m; ++j) {
      mat[i][j] = temp[j] - '0';
    }

  }

  for(int i = 0; i < n; ++i) {
    cin >> temp;
    for(int j = 0; j < m; ++j) {
      mat[i][j] ^= temp[j] - '0';
    }
  }

  int cnt = 0;
  for(int i = 0; i < n-2; ++i) {
    for(int j = 0; j < m-2; ++j) {
      if(mat[i][j] == 1) {
        flip(i, j, mat);
        cnt++;
      }
    }
  }

  if(isFinished(mat)) {
    cout << cnt << "\n";
  } else {
    cout << -1 << "\n";
  }

  return 0;
}