[JavaScript] 백준 골드 4 : 15683 - 감시

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

15683번: 감시

---

📌 작성한 코드 

// 15683
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] = input.shift().split(" ").map(Number);
let cctv = [];
let zeroCount = 0;
const initBoard = input.map((str, i) => {
    const temp = str.split(" ").map(Number);
    temp.forEach((val, j) => {
        if (val !== 0 && val !== 6) cctv.push([i, j]);
        if (val === 0) zeroCount++;
    });

    return temp;
});

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

const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];

const update = (x, y, dir) => {
    dir %= 4;
    while (true) {
        x += dx[dir];
        y += dy[dir];

        if (x < 0 || x >= N || y < 0 || y >= M || board[x][y] === 6) return;
        if (board[x][y] !== 0) continue;
        board[x][y] = "#";
    }
};

for (let i = 0; i < 1 << (2 * cctv.length); i++) {
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < M; y++) {
            board[x][y] = initBoard[x][y];
        }
    }

    let num = i;
    for (let j = 0; j < cctv.length; j++) {
        const [x, y] = cctv[j];

        const dir = num % 4;
        num = Math.floor(num / 4);

        if (board[x][y] === 1) {
            update(x, y, dir);
        } else if (board[x][y] === 2) {
            update(x, y, dir);
            update(x, y, dir + 2);
        } else if (board[x][y] === 3) {
            update(x, y, dir);
            update(x, y, dir + 1);
        } else if (board[x][y] === 4) {
            update(x, y, dir);
            update(x, y, dir + 1);
            update(x, y, dir + 2);
        } else {
            update(x, y, dir);
            update(x, y, dir + 1);
            update(x, y, dir + 2);
            update(x, y, dir + 3);
        }
    }

    let tempZeroCount = 0;
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < M; y++) {
            if (board[x][y] === 0) {
                tempZeroCount++;
            }
        }
    }
    if (zeroCount > tempZeroCount) zeroCount = tempZeroCount;
}

console.log(zeroCount);

 

📌 풀이 

가능한 cctv의 모든 방향을 다 적용해보고, 가장 작은 사각지대를 찾는 시뮬레이션(구현) 문제이다.

문제를 풀어보겠다고 dfs로 한참을 풀다가 너무 말도 안되는 풀이라는 생각이 들어서 다른 분의 풀이를 보고 다시 풀어보았다. 바킹독님의 알고리즘 강의를 보면서 알고리즘을 공부하고 있어서 해당 글을 보고 다시 풀어보았다. 

 

📌 참고 

https://blog.encrypted.gg/948

[실전 알고리즘] 0x0D강 - 시뮬레이션

 

cctv의 종류는 5개가 존재하고, 각 cctv가 바라볼 수 있는 방향은 4가지(상하좌우)가 있다.

문제를 풀기 위해서 cctv가 바라보는 방향들을 미리 정하고, 그 다음에 해당 방향으로 cctv가 볼 수 있는 부분을 채우면서 사각지대를 찾을 것이다. (방향을 미리 구하고 푸는 방법을 생각하지 못하고, dfs를 통해 각 cctv마다 가장 많은 부분을 보는 방향을 찾고, 해당 방향으로 cctv를 고정하고 다음 cctv의 방향을 찾는 방식을 택하려고 해서 초반에 잘 풀리지 않았다. 알고리즘은 아이디어 싸움이라는 생각이 들었던 문제..)

 

(1) 방향 구하기

cctv가 3개가 있다고 했을 때, 가능한 cctv의 방향 수는 4 * 4 * 4 = 4**3 = 64개이다. cctv가 4개 있을 경우는 4 ** 4 = 256개이다. 이를 통해 N개의 cctv가 있다고 했을 때 가능한 모든 방향의 수는 4 ** N 이라는 것을 알 수 있다. 그렇다면 우리는 각 숫자를 4진수로 표현했을 때 각 cctv의 방향을 구할 수 있게 된다. 

4의 N 제곱을 구하는 방법은 여러가지가 있는데 비트의 shift 연산을 사용해서도 구할 수 있다. (자바스크립트에서는 ** 거듭제곱 연산자를 제공하고 있기 때문에 해당 연산자를 사용해도 무방하다.) 오른쪽으로 1비트를 이동하면 현재수가 n이라고 했을 때 2의 n제곱을 구할 수 있다. 우리가 구하고자 하는 것은 4의 거듭제곱을 구하는 것이므로 2를 곱해주면 된다. 

1 << (2 * cctv.length)

 

(2) 방향에 따라 볼 수 있는 곳 확인하기

cctv는 종류에 따라 한번에 여러 방향을 볼 수 있긴 하지만, cctv가 볼 수 있는 방향은 동서남북 4방향으로 정해져있다. 그래서 각 방향에 따라 볼 수 있는 부분을 확인하는 함수를 작성할 것이다. 벽이 나오거나 범위를 벗어나기 전까지 cctv 방향을 기준으로 계속해서 이동하면서 볼 수 있는 부분을 '#'으로 채워나간다.

const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];

const update = (x, y, dir) => {
    dir %= 4;
    while (true) {
        x += dx[dir];
        y += dy[dir];

        if (x < 0 || x >= N || y < 0 || y >= M || board[x][y] === 6) return;
        if (board[x][y] !== 0) continue;
        board[x][y] = "#";
    }

 

(3) cctv의 종류에 따라 볼 수 있는 곳 채우기

우선 cctv가 볼 수 있는 부분을 기록하기 위해 board에 initBoard 상태를 복사해서 가져온다. 초기 상태를 설정해주는 작업이다.

for (let x = 0; x < N; x++) {
    for (let y = 0; y < M; y++) {
        board[x][y] = initBoard[x][y];
    }
}

그리고 구한 cctv의 종류에 따라서 종류에 따른 방향으로 시야를 확인하는 함수를 호출한다.

let num = i;
for (let j = 0; j < cctv.length; j++) {
    const [x, y] = cctv[j];

    const dir = num % 4; // 4진수로 만들어서 방향 구하기 (num은 현재 숫자 ex) 55, dir은 방향) 
    num = Math.floor(num / 4); // 다음 방향을 구하기 위해서 나눈 몫 저장

    if (board[x][y] === 1) { // cctv의 종류가 1번이면
        update(x, y, dir);
    } else if (board[x][y] === 2) { // 2번
        update(x, y, dir);
        update(x, y, dir + 2);
    } else if (board[x][y] === 3) { // 3번
        update(x, y, dir);
        update(x, y, dir + 1);
    } else if (board[x][y] === 4) { // 4번
        update(x, y, dir);
        update(x, y, dir + 1);
        update(x, y, dir + 2);
    } else { // 5번
        update(x, y, dir);
        update(x, y, dir + 1);
        update(x, y, dir + 2);
        update(x, y, dir + 3);

 

(4) 사각지대 확인하기

각 cctv의 방향에 따른 시야 탐색이 끝나고 나면, 이제 0으로 남아있는 부분(사각지대)의 수를 세어 줄 것이다. 우리는 가장 작은 사각지대의 수를 구하고 싶으므로 현재 상태의 0의 개수가 이전에 저장된 0의 개수보다 적으면 업데이트 해준다.

let tempZeroCount = 0;
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < M; y++) {
            if (board[x][y] === 0) {
                tempZeroCount++;
            }
        }
    }
    if (zeroCount > tempZeroCount) zeroCount = tempZeroCount;

 

✅ 성공