[JS] 백준 15683 : 감시

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

15683번: 감시

 

 

📋풀이방법

1. CCTV가 있는 곳의 좌표를 모두 저장한다

2. DFS를 이용해서 CCTV의 넘버에 따라 각각의 방향으로 뻗어나간다.

 -1번이면 4개의 방향 -> DFS 4개

 - 2번이면 2개의 방향 -> DFS 2개

 -3번이면 4개의 방향 -> DFS 4개

 - 4번이면 4개의 방향 -> DFS 4개

 - 5번이면 1개의 방향 -> DFS 1개

 -각 방향으로 뻗어나가는 DFS를 모두 구해야한다.

3. 각 CCTV의 방향을 #으로 바꿔줘야한다.

 -CCTV마다 각각 보는 방향이 다르므로 함수를 만들어서 각각 다른 방향을 보는 것을 해결했다.

 -각 열 또는 행에 6이 있으면 함수를 멈추고 0이 아닌 cctv가있으면 #으로 바꾸지않아야한다.

 -그 이외에는 #으로 한 방향을 모두 칠해준다.

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,M]=input.shift().split(" ").map(Number);

let arr=[]
for(var i=0;i<N;i++){
    arr.push(input.shift().split(" ").map(Number));
}
let cctv=[];
for(var i=0;i<N;i++){
    for(var j=0;j<M;j++){
        if(arr[i][j]!=0 && arr[i][j]!=6) cctv.push([i,j,arr[i][j]]);
    }
}

function checkRight(arr_t,y,x){
    for(var i=x+1;i<M;i++){
        if(arr_t[y][i]==6) return;
        if(arr_t[y][i]!=0) continue;
        arr_t[y][i]=-1;
    }
}
function checkLeft(arr_t,y,x){
    for(var i=x-1;i>=0;i--){
        if(arr_t[y][i]==6) return;
        if(arr_t[y][i]!=0) continue;
        arr_t[y][i]=-1;
    }
}
function checkUp(arr_t,y,x){
    for(var i=y-1;i>=0;i--){
        if(arr_t[i][x]==6) return;
        if(arr_t[i][x]!=0) continue;
        arr_t[i][x]=-1;
    }
}
function checkDown(arr_t,y,x){
    for(var i=y+1;i<N;i++){
        if(arr_t[i][x]==6) return;
        if(arr_t[i][x]!=0) continue;
        arr_t[i][x]=-1;
    }
}
let min=10000;
function DFS(L,tmap,cc){
    if(L == cc.length) {
        let count=0;
        for(var i=0;i<N;i++){
            for(var j=0;j<M;j++){
                if(tmap[i][j]==0) count++;
            }
        }
        min = Math.min(min,count);
        return;
    }
    
    let [y,x,ccNum]=cc[L];
    let temp=[];
    if(ccNum==1){
        temp=tmap.map(x=>[...x]);
        checkLeft(temp,y,x);
        DFS(L+1,temp,cc);

        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        DFS(L+1,temp,cc);

        temp=tmap.map(x=>[...x]);
        checkUp(temp,y,x);
        DFS(L+1,temp,cc);

        temp=tmap.map(x=>[...x]);
        checkDown(temp,y,x);
        DFS(L+1,temp,cc);
    }
    else if(ccNum==2){
        temp=tmap.map(x=>[...x]);
        checkLeft(temp,y,x);
        checkRight(temp,y,x);
        DFS(L+1,temp,cc);

        temp=tmap.map(x=>[...x]);
        checkUp(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1,temp,cc);

    }else if (ccNum == 3) {
        temp=tmap.map(x=>[...x]);
        checkLeft(temp, y,x);
        checkUp(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkUp(temp,y,x);
        checkRight(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkDown(temp,y,x);
        checkLeft(temp,y,x);
        DFS(L+1, temp, cc);
    }
    else if (ccNum == 4) {
        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        checkLeft(temp, y,x);
        checkUp(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkUp(temp,y,x);
        checkLeft(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        checkLeft(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkDown(temp,y,x);
        checkRight(temp,y,x);
        checkUp(temp,y,x);
        DFS(L+1, temp, cc);
    }else if(ccNum==5){
        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        checkLeft(temp, y,x);
        checkUp(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1, temp, cc);
    }
    
}
DFS(0,arr,cctv)
console.log(min)

 

 

💢어려웠던 점

1. CCTV마다 바로보는 방향이 다른 것을 해결하지 못했다. 

 -CCTV 좌표를 기준으로 상하좌우를 #으로 색칠하는 함수를 통해 해결해야했다.

2. DFS로 뻗어나갈 때 CCTV가 2개이상일 때는 각 4방향 또는 2방향, 1방향 에 대한 모든 경우의 수를 어떻게 계산해야하는지 파악하지 못했다.

  -만약 1번 과 2번 CCTV가 있다면

 - 1번의 4방향 2번의 2방향 4*2=8가지의 경우의 수를 모두 구해야한다.

 -이는 DFS를 각각의 볼 수 있는 방향에 따라 map을 복사하면서 모두 뻗어 나가주면 된다.

-예시 4번일때

 if (ccNum == 4) {
        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        checkLeft(temp, y,x);
        checkUp(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkUp(temp,y,x);
        checkLeft(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkRight(temp,y,x);
        checkLeft(temp,y,x);
        checkDown(temp,y,x);
        DFS(L+1, temp, cc);

        temp=tmap.map(x=>[...x]);
        checkDown(temp,y,x);
        checkRight(temp,y,x);
        checkUp(temp,y,x);
        DFS(L+1, temp, cc);
    }