[백준] 15683번 - 감시 Javascript(NodeJs)

문제 링크

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

풀이

알고리즘: 브루트포스, 시뮬레이션

소스코드

let fs =require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [N, M] = inputData[0].trim().split(' ').map(x=>x*1);
let office = new Array(N);
for(let i=0; i<N; i++) {
    office[i] = new Array(M);
}
for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split(' ').map(x=>x*1);
    for(let j=0; j<input.length; j++) {
        office[i-1][j] = input[j];
    }
}
let dir = new Array(6);
dir[1] = new Array(4);
dir[2] = new Array(2);
dir[3] = new Array(4);
dir[4] = new Array(4);
dir[5] = new Array(1);
dir[1][0] = [0];
dir[1][1] = [1];
dir[1][2] = [2];
dir[1][3] = [3];
dir[2][0] = [3,1];
dir[2][1] = [0,2];
dir[3][0] = [0,1];
dir[3][1] = [1,2];
dir[3][2] = [2,3];
dir[3][3] = [3,0];
dir[4][0] = [0,1,3];
dir[4][1] = [0,1,2];
dir[4][2] = [1,2,3];
dir[4][3] = [0,2,3];
dir[5][0] = [0,1,2,3];

let cctv_arr = [];
for(let i=0; i<office.length; i++) {
    for(let j=0; j<office[i].length; j++) {
        if(1<=office[i][j] && office[i][j]<=5) {
            cctv_arr.push({cctv:dir[office[i][j]], x: j, y:i});
        }
    }
}
let bc_arr = []; //blind count arr;
if(cctv_arr.length >=1){
    bs_find(cctv_arr.length - 1, office);
} else {
    bc_arr.push(zero_cout(office));
}
function bs_find(index, of_arr) {
    let cctv = cctv_arr[index].cctv;
    let x = cctv_arr[index].x;
    let y = cctv_arr[index].y;
    if(index === 0) {
        for(let i=0; i<cctv.length; i++) {
            let copy = of_arr.map(v => [...v]);
            bc_arr.push(zero_cout(blind_check(cctv, x, y, i, copy)));
        }
    } else {
        for(let i=0; i<cctv.length; i++) {
            let copy = of_arr.map(v => [...v]);
            bs_find(index-1, blind_check(cctv, x, y, i, copy));
        }
    }
}
function blind_check(cctv,x,y,j,of_arr) {
    for(let i=0; i<cctv[j].length; i++) {
        paint(x,y, cctv[j][i], of_arr);
    }
    return of_arr;
}

function paint(x, y, dir, of_arr) {
    //dir 0 위쪽, dir 1 오른쪽, dir 2 아래, dir 3 왼쪽
    if(dir === 0) {
        for(let i=y-1; i>=0; i--) {
            if(of_arr[i][x] === 6) {
                break;
            } else if(of_arr[i][x] === 0) {
                of_arr[i][x] = '#';
            }
        }
    } else if(dir === 1) {
        for(let i=x+1; i<M; i++) {
            if(of_arr[y][i] === 6) {
                break;
            } else if(of_arr[y][i] === 0) {
                of_arr[y][i] = '#';
            }
        }
    } else if(dir === 2) {
        for(let i=y+1; i<N; i++) {
            if(of_arr[i][x] === 6) {
                break;
            } else if(of_arr[i][x] === 0) {
                of_arr[i][x] = '#';
            }
        }
    } else if(dir === 3) {
        for(let i=x-1; i>=0; i--) {
            if(of_arr[y][i] === 6) {
                break;
            } else if(of_arr[y][i] === 0) {
                of_arr[y][i] = '#';
            }
        }
    }
}

function zero_cout(arr) {
    let cout = 0;
    for(let j=0; j<N; j++) {
        for(let k=0; k<M; k++) {
            if(arr[j][k] === 0) {
                cout += 1;
            }
        }
    }
    return cout;
}
console.log(Math.min(...bc_arr));