백준15683 : 감시 - javascript(백트리킹,좋은문제)

문제 출처

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

 

정답 풀이 

다른 분의 코드를 참고했다.. !

좋은 문제다. 

정답 코드

const [nums, ...arr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,m] = nums.split(' ').map(v => +v); 
let board = arr.map(el => el.split(' ').map(v => +v));

const dir = [[-1,0],[0,1],[1, 0],[0,-1]]
const dirType = [0,[0], [0,2], [0,1], [0,1,2], [0,1,2,3]]
const cctv = []; 
let minSize = Number.MAX_SAFE_INTEGER; 

for(let i =0; i<n; i++){
    for(let j=0; j<m; j++){
        if(board[i][j] !== 0 && board[i][j] !== 6) cctv.push([i,j])    
    }
}

//현재 방향에서 가능한 영역 탐색 
function watch(x,y,type, startDir){
  const dirToWatch = dirType[type]
  
  for(let d of dirToWatch){
      const curDir = (startDir + d) % 4 
      let sx = x; 
      let sy = y; 
      
      while(true){
          const nx = sx + dir[curDir][0]
          const ny = sy + dir[curDir][1]
          
          sx = nx 
          sy = ny
          
          if(nx <0 || ny <0 || nx>=n|| ny >=m) break
          if(board[nx][ny] === 6) break; 
          if(board[nx][ny] !== 0) continue; 
       
          board[nx][ny] = -1
      }
  }
}

function dfs(L){
       if(L === cctv.length){
           let size = 0; 
           for(let i=0; i<n; i++){
               for(let j=0; j<m; j++){
                   if(board[i][j] === 0) size++; 
               }
           }
           minSize =  Math.min(minSize, size)
           return; 
       }else{
           const [x,y] = cctv[L]
           for(let k=0; k<4; k++){
               const tmp = [...board.map((row) => [...row])]
               watch(x,y,board[x][y], k)
               dfs(L+1)
               board = [...tmp.map(el => [...el])]
           }
       }
}

dfs(0)
console.log(minSize)