문제

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

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

입력

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

출력

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

예제 입력

3 4
0000
0010
0000
1001
1011
1001

예제 출력

2

내가 했던 풀이 방법

1. 현재 행렬 상태와 만들어야 하는 행렬 상태를 current와 goal에 각각 저장한다.
2. current와 goal의 각 상태를 비교해서 같을 경우 0, 다를 경우 1로 저장하여 diff 배열에 저장한다.
3. count를 0으로 초기화해주고, diff 배열을 순차적으로 돌면서 diff[i][j]가 1일 경우, 해당 값을 첫 번째 줄 가장 왼쪽 요소로 둔 3×3 배열이라고 생각하고 값을 swap 해준다. 해당 값이 1일 경우에는 무조건 뒤집어져야 하기 때문이다. 이때, 해당 값을 기준으로 3×3 배열을 만들어낼 수 없을 때 (index 범위를 넘어갈 때) 해당 행렬로 만들 수 없음이 확정된 것이므로 count를 -1로 저장하고 반복문을 탈출한다.
4. 모든 반복이 끝난 뒤 count를 출력한다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let [N, M] = n.trim().split(' ').map(Number);
let current = input.slice(0, N);
let goal = input.slice(N);
let diff = [];

for (let i = 0; i < N; i++) {
  current[i] = current[i].trim().split('').map(Number);
  goal[i] = goal[i].trim().split('').map(Number);
  let col = [];
  for (let j = 0; j < M; j++) {
    if (current[i][j] === goal[i][j]) col.push(0);
    else col.push(1);
  }
  diff.push(col);
}

let count = 0;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (diff[i][j] === 1) {
      if (i + 2 < N && j + 2 < M) {
        for (let k = i; k < i + 3; k++) {
          for (let l = j; l < j + 3; l++) {
            diff[k][l] = diff[k][l] === 1 ? 0 : 1;
          }
        }
        count++;
      } else {
        count = -1;
        break;
      }
    }
  }
  if (count === -1) break;
}

console.log(count);

회고

생각보다 알고리즘 풀이는 간단했지만, 처음에는 current와 goal로만 비교하고 swap하려고 했는데 다른 풀이들을 참고해보니 current와 goal을 비교한 diff를 활용하면 swap하는 과정에서도 좀 더 직관적을 것 같아서 이 풀이를 기억해보고자 기록한다.