[백준] 18428 감시 피하기 - Node.js

18428번: 감시 피하기

POINT

조합 Combinations

빈 좌표 배열에서 3개를 뽑는 조합을 사용하여, 장애물을 세운다.

DFS

장애물을 세운 후, 선생님을 상하좌우로 한 칸씩 계속 이동시킨다.

 

1. 장애물을 만나거나 벽에 다다르면, 다른 방향 감시하기
2. 학생을 만나면, 감시를 종료하고 결과("NO") 출력하기

문제풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const n = Number(input[0]);
// 그래프 생성
let graph = [];
input.slice(1).forEach(ele => {
    graph.push(ele.split(" "));
})

// 빈칸, 선생님 좌표 저장
let blankList = [];
let teacherList = [];
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (graph[i][j] === "X") {
            blankList.push([i, j]);
        } else if (graph[i][j] === "T") {
            teacherList.push([i, j]);
        }
    }
}

// 장애물 위치 3개를 뽑는 조합
const objectCombinations = getCombinations(blankList, 3);
let isCheck = true; // 학생이 감시되면 true
for (const [[x1, y1], [x2, y2], [x3, y3]] of objectCombinations) {
    // 장애물 설치
    graph[x1][y1] = graph[x2][y2] = graph[x3][y3] = "O";
    // 선생님 감시 시작 (학생을 만나는지 아닌지 반환)
    isCheck = checkStudent(graph, teacherList);
    // 선생님이 학생을 만나지 못했으면 중단
    if (!isCheck) {
        break;
    }
    graph[x1][y1] = graph[x2][y2] = graph[x3][y3] = "X"; // 장애물 되돌리기
}

if (isCheck) {
    console.log("NO");    
} else {
    console.log("YES");    
}

//////////////////////// 함수 구현

function getCombinations(arr, selectNum) {
    let result = [];
    
    if (selectNum === 1) {
        return arr.map(ele => [ele]);
    }
    
    arr.forEach((fixed, index, origin) => {
        const rest = arr.slice(index+1);
        const combinations = getCombinations(rest, selectNum - 1);
        const attached = combinations.map(ele => [fixed, ...ele]);
        result.push(...attached);
    })
    
    return result;
}

function checkStudent(graph, teacherList) {
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    // 선생님이 이동한 위치
    let nx = 0; 
    let ny = 0;
    for (const [x, y] of teacherList) {
        // 상하좌우 한 방향씩 계속 이동
        for (let i = 0; i < 4; i++) {
            // 선생님 원위치
            nx = x;
            ny = y;
            while (true) {
                nx += dx[i];
                ny += dy[i];
                
                // 그래프 범위를 벗어나면 중단
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                    break;
                }
                // 장애물을 만나면 중단
                if (graph[nx][ny] === "O") {
                    break;
                } 
                // 학생을 만나면 종료 true
                if (graph[nx][ny] === "S") {
                    return true;
                }
            } 
        }
    }
    return false; // 학생을 만나지 못했으면 false
}