[백준 18428] 감시 피하기

문제

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

아이디어

전체 맵에서 선생님이 존재하는 위치와 장애물을 설치할 수 있는 비어있는 공간의 위치를 2차원 배열로 각각 저장한다.
비어있는 공간에 장애물을 3군데 설치하는 경우의 수를 조합을 통해 구한다.
각 경우의 수마다 장애물을 설치한다.
1. 선생의 위치로부터 상하좌우로 학생을 탐지하는 로직을 수행한다.
2. 만약 학생을 발견했다면 중단하고 다음 경우의 수로 넘어간다.
3. 만약 모든 선생이 학생을 발견하지 못했다면 프로그램의 결과를 'YES'로 한다.
설치한 장애물을 다시 제거하고 다음 경우의 수를 진행한다.

풀이중 막혔던 부분

선생이 학생을 발견했을 때 로직을 중단하고 다음 경우의 수로 진행하게 만드는 과정에서 한 선생이 학생을 발견했을 때 다음 경우의 수로 넘어가는 것이 아니라, 같은 경우의 수의 다른 선생 위치로부터 탐색을 시작하게 구현해서 문제가 생겼었다.

소스코드

// 입력 처리
const INPUT_NAME = 'i2.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require('fs').readFileSync(filePath).toString().trim().split('\n').map(item => item.trim());
const n = Number(input[0]);
const map = input
  .filter((_, i) => i > 0)
  .map(e => e.split(' '));

const spaces = [];
const teachers = [];
let programResult = 'NO';
map.forEach((row, y) => {
  row.forEach((item, x) => {
    if (item === 'X') spaces.push([y, x]);
    if (item === 'T') teachers.push([y, x]);
  });
});

// 맵 영역 내부인지 확인하는 함수
function isInBoundary(y, x) {
  if (y >= n || y < 0) return false;
  if (x >= n || x < 0) return false;
  return true;
}

// 특정 좌표들의 값을 바꾸는 함수. 맵에 장애물을 설치하거나 해제할 수 있음.
function setMapData(comb, char) {
  comb.forEach(([y, x]) => {
    map[y][x] = char;
  });
}

// 한쪽 방향 탐지 로직
function detech(y, x, dy, dx) {
  let nowY = y + dy;
  let nowX = x + dx;

  while (isInBoundary(nowY, nowX)) {
    if (map[nowY][nowX] === 'O') break; // 벽을 만나면 현재 방향 탐색 종료
    if (map[nowY][nowX] === 'S') return true; // 학생을 만나면 true 반환하여 함수 종료

    nowY += dy;
    nowX += dx;
  }

  return false;
}

// 선생님이 학생을 발견할 수 있는지 탐지
function detectStudent(teachers) {
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // dy, dx

  for (let [y, x] of teachers) { // 각 선생님마다 학생 탐지
    for (let [dy, dx] of directions) { // 상하좌우 네 방향으로 탐지
      if (detech(y, x, dy, dx)) return true; // 학생을 탐지했으면 true 반환하여 함수 종료
    }
  }

  return false; // 네 방향 탐색했을 때 아무 학생도 찾지 못했다면 false 반환
}

// 경우의 수 발견시 콜백
function onFindCase(comb) {
  setMapData(comb, 'O'); // 장애물 설치

  // 어떤 선생도 학생을 탐지하지 못했다면 결과를 'YES'로 함
  if (detectStudent(teachers) === false) return programResult = 'YES';

  setMapData(comb, 'X'); // 장애물 해제
}
  
// 조합으로 경우의 수 구하기
function combination(arr, r) {
  const result = Array.from({ length: r }, () => 0);

  function dfs(depth, begin) {
    if (programResult === 'YES') return; // 이미 프로그램 결과 구했으면 로직 중단
    if (depth === r) return onFindCase(result); // 구한 경우의 수를 가지고 로직 수행

    for (let i = begin; i < arr.length; i++) {
      result[depth] = arr[i];
      dfs(depth + 1, i + 1);
    }
  }

  dfs(0, 0);
}

// 문제
function solution() {
  combination(spaces, 3);
  console.log(programResult);
}

// 실행
solution();