[백준] 18428 감시 피하기(JS)

 

18428번: 감시 피하기

 

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

연구소 문제와 비슷하다.

 

백트래킹 문제이며, 장애물을 설치하는 데에는 DFS, 감시를 피할 수 있는지의 여부는 BFS로 풀이하였다.

const fs = require('fs');
let [N, ...input] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let board = input.map((v) => v.split(' '));
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let flag = false;
function checkBoard(arr) {
    let queue = [];
    for(let i=0; i<N; i++) {
        for(let j=0; j<N; j++) {
        // 선생님의 모든 위치를 큐에 저장한다.
            if(arr[i][j] === 'T') {
                queue.push([i, j]);
            }        
        }
    } 
    for(let i=0; i<queue.length; i++) { // 선생님의 위치
        for(let j=0; j<4; j++) { // 상하좌우
            let [nx, ny] = queue[i];
            while(nx >= 0 && ny >= 0 && nx < N && ny < N) {
            	// 장애물일 경우 다음 좌표를 검사한다.
                if(arr[nx][ny] === 'O') break;
                // 학생일 경우
                if(arr[nx][ny] === 'S') return false;
                // 상하좌우 방향을 계속 탐색한다.
                nx += dx[j];
                ny += dy[j];
            }
        }
    }
    return true;
}
function dfs(L) {
    if(L === 3) { // 장애물을 3개 설치한 경우
        let res = checkBoard(board.map((v) => [...v]));
        if(res) {
		// 모든 학생들이 감시로부터 피할 수 있는 경우
            flag = true;
            return;
        }
    }
    else {
        for(let i=0; i<N; i++) {
            for(let j=0; j<N; j++) {
                if(board[i][j] === 'X') {
                    board[i][j] = 'O';
                    dfs(L + 1);    
                    board[i][j] = 'X';
                }
            }
        }
    }
}
dfs(0);
if(flag) console.log('YES');
else console.log('NO');