2차원 동전 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

1. 한 번 뒤집었던 행/열을 또 한번 뒤집어봤자 같은 결과
2. 경우의 수는 1. 행을 뒤집어 보고 열을 뒤집기 , 2. 열을 뒤집어 보고 행을 뒤집기
3. 예를 들어서 2의 경우의 수를 더 딥하게 나눠보면 한 행의 모든 동전이 목표의 행에 있는 모든 동전과 모두 반대이거나, 모두 같다면 원하는 바를 이룰 수 있음 
4. 따라서, 2의 경우의 수를 더 나눠보면
   1. 행의 첫번째 요소들을 기준으로 
      1. 목표의 행과 다른 경우 행을 뒤집고, 그 다음 열을 뒤집기
      2. 목표의 행과 같은 경우 행을 뒤집고, 그 다음 열을 뒤집기
   2. 열의 첫번째 요소들을 기준으로
      1. 목표의 열과 다른 경우 열을 뒤집고, 행을 뒤집기
      2. 목표의 열과 같은 경우 열을 뒤집고, 행을 뒤집기
5.  4의 경우의 수를 통해 얻을 수 있는 횟수들 중 가장 작은 값을 리턴

const turnBack = (gr, line, arr) => {
    const n = gr.length;
    const m = gr[0].length;

    if (line === 'row') {
        arr.forEach((num) => {
            for (let i = 0; i < m; i++) {
                gr[num][i] = gr[num][i] === 0 ? 1 : 0;
            }
        });
    } else {
        arr.forEach((num) => {
            for (let i = 0; i < n; i++) {
                gr[i][num] = gr[i][num] === 0 ? 1 : 0;
            }
        });
    }
};
function solution(beginning, t) {
    const n = beginning.length;
    const m = beginning[0].length;
    let answer = Number.MAX_SAFE_INTEGER;
    const target = JSON.stringify(t);
    const r = [];
    const c = [];
    const r1 = [];
    const c1 = [];
    const q = [];
    for (let i = 0; i < n; i++) {
        if (beginning[i][0] !== t[i][0]) r.push(i);
        else r1.push(i);
    }
    for (let j = 0; j < m; j++) {
        if (beginning[0][j] !== t[0][j]) c.push(j);
        else c1.push(j);
    }

    q.push([[...r], 'row', 0, r.length, beginning.map((b) => [...b])]);
    q.push([[...r1], 'row', 0, r1.length, beginning.map((b) => [...b])]);
    q.push([[...c], 'col', 0, c.length, beginning.map((b) => [...b])]);
    q.push([[...c1], 'col', 0, c1.length, beginning.map((b) => [...b])]);

    while (q.length) {
        const [arr, line, num, cnt, gr] = q.shift();

        if (num >= 2) continue;
        turnBack(gr, line, arr);

        if (JSON.stringify(gr) === target) {
            answer = Math.min(answer, cnt);
            continue;
        }

        if (line === 'row') {
            const c = [];
            for (let j = 0; j < m; j++) {
                if (gr[0][j] !== t[0][j]) c.push(j);
            }
            q.push([
                [...c],
                'col',
                num + 1,
                cnt + c.length,
                gr.map((b) => [...b]),
            ]);
        }
        if (line === 'col') {
            const c = [];
            for (let j = 0; j < n; j++) {
                if (gr[j][0] !== t[j][0]) c.push(j);
            }
            q.push([
                [...c],
                'row',
                num + 1,
                cnt + c.length,
                gr.map((b) => [...b]),
            ]);
        }
    }

    return answer !== Number.MAX_SAFE_INTEGER ? answer : -1;
}

console.log(
    solution(
        [
            [0, 1, 0, 0, 0],
            [1, 0, 1, 0, 1],
            [0, 1, 1, 1, 0],
            [1, 0, 1, 1, 0],
            [0, 1, 0, 1, 0],
        ],
        [
            [0, 0, 0, 1, 1],
            [0, 0, 0, 0, 1],
            [0, 0, 1, 0, 1],
            [0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1],
        ]
    )
);