백준 1080 행렬

문제

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

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

제한 사항

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

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const sol = (input) => {
  const [row, column] = input.shift().split(" ").map(Number);
  const arrA = input.slice(0, row).map((e) => e.split("").map(Number));
  const arrB = input.slice(row).map((e) => e.split("").map(Number));
  
  // 두 행렬을 비교하는 함수
  const compareMatrix = (listA, listB) => {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < column; j++) {
        if (listA[i][j] !== listB[i][j]) return false;
      }
    }
    return true;
  };
   // 같을 수도 있으니 비교해보기
  if (compareMatrix(arrA, arrB)) return 0;

  // 뒤집는 함수
  const flip = (x, y) => {
    for (let i = x; i < x + 3; i++) {
      for (let j = y; j < y + 3; j++) {
        arrA[i][j] = 1 - arrA[i][j];
      }
    }
  };

  let cnt = 0;
  for (let i = 0; i < row - 2; i++) {
    for (let j = 0; j < column - 2; j++) {
      if (arrA[i][j] !== arrB[i][j]) {
        flip(i, j);
        cnt++;
        // 뒤집고 확인하기
        if (compareMatrix(arrA, arrB)) return cnt;
      }
    }
  }

  // 다 빠져나오면 행렬이 같이지지 못한 것
  return -1;
};

console.log(sol(input));

두 행렬을 비교하면서 다르다면 뒤집는다. 이때 범위는 행과 열 각각 -2를 해줘도 된다. 안하게되면 행렬의 범위를 넘어가는 연산이 생겨 오류가 생길지도 모른다. (테스트는 안해봤다.)

3 x 3행렬의 범위만큼 뒤집어가면서 비교한다. 뒤집고 확인해서 같으면 cnt값을 리턴하고 이때 반복문을 빠져나오면 같아지지 못한 것임으로 -1을 출력한다.