Programmers_84021 퍼즐 조각 채우기

// DFS로 연결된 칸(빈 공간 혹은 블록)의 좌표를 구해 반환하는 함수
function getShape(startX, startY, base, target) {
    const stack = [[startX, startY]];
    const shape = [[startX, startY]];
    const delta = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
    ];

    while (stack.length) {
        const [x, y] = stack.pop();
        delta.forEach(([dx, dy]) => {
            if (base[y + dy]?.[x + dx] === target) {
                const [nx, ny] = [x + dx, y + dy];
                base[ny][nx] = Number(!target);
                stack.push([nx, ny]);
                shape.push([nx, ny]);
            }
        });
    }
    return shape;
}

// 모양 비교를 위해 해당 모양을 감싸는 박스를 생성하는 함수
// 왼쪽 위를 (0, 0)으로 1이 모양에 해당하는 부분, 0이 해당하지 않는 부분
function createBox(shape) {
    const [minX, minY, maxX, maxY] = shape.reduce(
        (acc, curr) => [
            Math.min(acc[0], curr[0]),
            Math.min(acc[1], curr[1]),
            Math.max(acc[2], curr[0]),
            Math.max(acc[3], curr[1]),
        ],
        [...shape[0], ...shape[0]]
    );
    const normalized = shape.map(([x, y]) => [x - minX, y - minY]);
    const box = Array.from(new Array(maxY - minY + 1), () =>
        new Array(maxX - minX + 1).fill(0)
    );
    normalized.forEach(([x, y]) => (box[y][x] = 1));

    return box;
}

// 블록을 90도 회전시키는 함수
function rotate90(shape) {
    return shape.map(([x, y]) => [-y, x]);
}

// 두 박스가 일치하는지 확인하는 함수
function isEqual(a, b) {
    if (a.length !== b.length || a[0].length !== b[0].length) return false;
    return a.every((row, j) => row.every((col, i) => col === b[j][i]));
}

// 공간에 블록을 끼워넣을 수 있는지 확인하는 함수
// 블록을 90도씩 돌려가면서 piece의 box와 블록의 box가 일치하면 true를 반환
function isFit(a, b) {
    const boxA = createBox(a);

    for (let i = 0; i < 4; i += 1) {
        const boxB = createBox(b);
        if (isEqual(boxA, boxB)) return true;
        b = rotate90(b);
    }
    return false;
}

function solution(game_board, table) {
    const spaces = [];
    const pieces = [];
    for (let y = 0; y < game_board.length; y += 1) {
        for (let x = 0; x < game_board[0].length; x += 1) {
            if (!game_board[y][x]) {
                game_board[y][x] = 1;
                spaces.push(getShape(x, y, game_board, 0));
            }
            if (table[y][x]) {
                table[y][x] = 0;
                pieces.push(getShape(x, y, table, 1));
            }
        }
    }

    // 공간과 블록의 사용 여부를 확인하는 배열
    const spaceUsed = new Array(spaces.length).fill(0);
    const pieceUsed = new Array(pieces.length).fill(0);

    // 사용된 블록의 개수
    let count = 0;
    spaces.forEach((space, i) => {
        pieces.forEach((piece, j) => {
            if (!spaceUsed[i] && !pieceUsed[j] && isFit(space, piece)) {
                count += piece.length;
                spaceUsed[i] = 1;
                pieceUsed[j] = 1;
            }
        });
    });

    return count;
}