15683 감시 (자바스크립트)

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

문제 분석

우선 네 방향의 dir 배열을 만들어준다.

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];
// 우,하,좌,상

그 다음으로는 카메라의 넘버에 맞춰 바라볼 수 있는 방향을 담은 배열을 만들어준다.

const camera = [
    [],
    [[0], [1], [2], [3]],	//	1번
    [
	    [0, 2],				
        [1, 3], // 2번
    ],
    [
        [0, 1],  // 3번
        [1, 2],
        [2, 3],
        [3, 0],
    ],
    [
        [3, 0, 1], // 4번
        [0, 1, 2],
        [1, 2, 3],
        [2, 3, 0],
    ],
    [[0, 1, 2, 3]], // 5번
];

카메라가 담긴 좌표들을 담은 배열을 만든 뒤에 그 순서대로 카메라가 바라 볼 수 있는 지역들을 다 100으로 방문 처리한다.

방문 처리했다면 그 다음 카메라가 바라 볼 수 있는 곳들을 방문 처리하는 재귀의 형태를 만들어준다.

마지막 카메라까지 다 쳐리했다면 이제 그래프에서 0의 카운터를 answer와 비교하여 최솟값을 출력해주면 된다.

정답 코드

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];
// 우,하,좌,상
const camera = [
    [],
    [[0], [1], [2], [3]],
    [
        [0, 2],
        [1, 3],
    ],
    [
        [0, 1],
        [1, 2],
        [2, 3],
        [3, 0],
    ],
    [
        [3, 0, 1],
        [0, 1, 2],
        [1, 2, 3],
        [2, 3, 0],
    ],
    [[0, 1, 2, 3]],
];

const main = (n, m, gr) => {
    let answer = n * m;
    const coordinate = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] > 0 && gr[i][j] < 6) {
                coordinate.push([i, j]);
            }
        }
    }

    const visit = (x, y, dir, game) => {
        const nx = x + dx[dir];
        const ny = y + dy[dir];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) return;
        if (game[nx][ny] === 6) return;
        if (game[nx][ny] === 0) game[nx][ny] = 100;
        visit(nx, ny, dir, game);
    };
    const dfs = (idx, game) => {
        if (idx === coordinate.length - 1) {
            let s = 0;
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < m; j++) {
                    if (game[i][j] === 0) {
                        s++;
                    }
                }
            }
            answer = Math.min(answer, s);
            return;
        }
        const [cx, cy] = coordinate[idx + 1];
        const cameraArray = camera[game[cx][cy]];

        for (let i = 0; i < cameraArray.length; i++) {
            const gg = game.map((g) => [...g]);
            for (const dir of cameraArray[i]) {
                visit(cx, cy, dir, gg);
            }
            dfs(idx + 1, gg);
        }
    };
    const v = gr.map((r) => [...r]);
    dfs(-1, v);

    console.log(answer);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map((v) => +v);
const gr = input.slice(1).map((v) => v.split(' ').map((v) => +v));
main(n, m, gr);