[JavaScript] 백준 골드 3 : 18808 - 스티커 붙이기

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

18808번: 스티커 붙이기

---

📌 작성한 코드 

// 18808
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M, K] = input.shift().split(" ").map(Number);
const stickers = [];
for (let i = 0; i < K; i++) {
    const [r, _] = input.shift().split(" ").map(Number);
    const temp = [];
    for (let j = 0; j < r; j++) {
        temp.push(input.shift().split(" ").map(Number));
    }
    stickers.push(temp);
}

const computer = Array.from({ length: N }, () => new Array(M).fill(false));

// 1. 가장 왼쪽 위에 붙이기
// 2. 붙일 공간이 없다면 90도 회전하고 반복
// 3. 노트북에 몇 개의 칸이 채워졌는지 확인하기

const putSticker = (sticker) => {
    const row = sticker.length;
    const col = sticker[0].length;

    for (let i = 0; i <= N - row; i++) {
        for (let j = 0; j <= M - col; j++) {
            let flag = false;
            for (let x = i; x < i + row; x++) {
                for (let y = j; y < j + col; y++) {
                    if (sticker[x - i][y - j] === 1 && computer[x][y]) {
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }

            if (!flag) {
                for (let x = i; x < i + row; x++) {
                    for (let y = j; y < j + col; y++) {
                        if (!computer[x][y] && sticker[x - i][y - j] === 1) {
                            computer[x][y] = true;
                        }
                    }
                }
                return true;
            }
        }
    }

    return false;
};

const rotate = (sticker, count) => {
    const row = sticker.length;
    const col = sticker[0].length;

    count %= 4;
    if (count === 0) return sticker;

    const rotated = [];
    const rc = count % 2 === 0 ? [row, col] : [col, row];

    for (let i = 0; i < rc[0]; i++) {
        rotated[i] = new Array(rc[1]);
        for (let j = 0; j < rc[1]; j++) {
            if (count === 1) rotated[i][j] = sticker[row - j - 1][i];
            else if (count === 2) rotated[i][j] = sticker[row - i - 1][col - j - 1];
            else rotated[i][j] = sticker[j][col - i - 1];
        }
    }

    return rotated;
};

for (let i = 0; i < K; i++) {
    const sticker = stickers[i];

    for (let j = 0; j < 4; j++) {
        const tempSticker = rotate(sticker, j);
        const isAttacted = putSticker(tempSticker);
        if (isAttacted) break;
    }
}

let answer = 0;
for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (computer[i][j]) answer++;
    }
}

console.log(answer);

 

📌 풀이

스티커를 회전하며 노트북에 붙이면서 노트북에 스티커가 붙은 칸의 수를 구하는 문제이다.

 

스티커를 붙이는 방법은 다음과 같다.

(1) 다른 스티커와 겹치지 않고, 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다.
- 위치가 여러개라면 가장 왼쪽 상단에 위치하는 곳에 붙인다.
(2) 스티커를 붙일 수 있는 공간이 없다면, 스티커를 시계 방향으로 90도 회전하여 다시 가능한 위치를 찾는다.
- 찾지 못했으면 180,270도 회전한 상태에서도 찾아본다. 그렇게 하고도 찾지 못했으면 해당 스티커는 붙이지 않는다.
(3) 스티커가 붙여져있는 칸의 수를 센다.

 

(1) 스티커를 붙일 수 있는 위치를 찾는다.

해당 범위동안 반복문을 돌면서 스티커를 붙일 수 있는지 확인한다. 스티커를 붙여야 하는데, 해당 위치에 이미 다른 스티커가 있어서 스티커를 붙일 수 없다면 flag를 true로 바꿔서 스티커를 붙일 수 없다는 것을 표시해준다. 

 

그리고 반복문을 다 돌고 나서도 스티커를 붙일 수 있다는 것이 확인되면(`flag === false`) 다시 반복문을 돌며 해당 위치에 스티커를 붙여준다. 

const putSticker = (sticker) => {
    const row = sticker.length;
    const col = sticker[0].length;

    for (let i = 0; i <= N - row; i++) {
        for (let j = 0; j <= M - col; j++) {
            let flag = false;
            for (let x = i; x < i + row; x++) {
                for (let y = j; y < j + col; y++) {
                    if (sticker[x - i][y - j] === 1 && computer[x][y]) {
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }

            if (!flag) {
                for (let x = i; x < i + row; x++) {
                    for (let y = j; y < j + col; y++) {
                        if (!computer[x][y] && sticker[x - i][y - j] === 1) {
                            computer[x][y] = true;
                        }
                    }
                }
                return true;
            }
        }
    }

    return false;
};

(2) 스티커를 회전하는 함수 작성하기

스티커를 회전하는 함수는 다른 블로그의 도움을 받아 작성하였다. 해당 글을 통해 더 잘 이해할 수 있을 것이다. 

https://velog.io/@cptkuk91/2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-K%EB%B2%88-%ED%9A%8C%EC%A0%84-%EC%8B%9C%ED%82%A4%EA%B8%B0-rotateMatrix-Javascript

2차원 배열 K번 회전 시키기 rotateMatrix, Javascript

const rotate = (sticker, count) => {
    const row = sticker.length;
    const col = sticker[0].length;

    count %= 4;
    if (count === 0) return sticker;

    const rotated = [];
    const rc = count % 2 === 0 ? [row, col] : [col, row];

    for (let i = 0; i < rc[0]; i++) {
        rotated[i] = new Array(rc[1]);
        for (let j = 0; j < rc[1]; j++) {
            if (count === 1) rotated[i][j] = sticker[row - j - 1][i];
            else if (count === 2) rotated[i][j] = sticker[row - i - 1][col - j - 1];
            else rotated[i][j] = sticker[j][col - i - 1];
        }
    }

    return rotated;
};

 

(3) 스티커 붙이기 

스티커의 개수만큼 반복문을 돌면서, 해당 스티커를 붙이고 -> 회전해서 붙여보고를 반복하며 최종적으로 노트북에 붙여진 스티커를 구한다.

for (let i = 0; i < K; i++) {
    const sticker = stickers[i];

    for (let j = 0; j < 4; j++) {
        const tempSticker = rotate(sticker, j);
        const isAttacted = putSticker(tempSticker);
        if (isAttacted) break;
    }
}

let answer = 0;
for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (computer[i][j]) answer++;
    }
}

console.log(answer);

 

✅ 성공