Baekjoon 18428번 감시 피하기

문제

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

걸린 시간

-

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const n = parseInt(input());
const arr = [];
for(let i = 0; i < n; i++){
  arr.push(input().split(' '));
}

const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];

const chk = () => {
  let valid = true;
  for(let y = 0; y < n; y++){
    for(let x = 0; x < n; x++){
      if(arr[y][x] === 'S'){
        for(let i = 0; i < 4; i++){
          let T = false;
          let cy = y;
          let cx = x;
          while(true){
            cy += dy[i];
            cx += dx[i];
            if(cy < 0 || cy >= n || cx < 0 || cx >= n) break;
            if(arr[cy][cx] === 'O') break;
            if(arr[cy][cx] === 'T'){
              T = true;
              break;
            }
          }
          if(T) valid = false;
        }
      }
    }
  }
  if(valid) return 1;
  else return 0;
}

const solve = (l, O) => {
  // 기저 사례
  if(O === 3) return chk();
  // 재귀 호출
  let ret = 0;
  for(let loc = l+1; loc < n*n; loc++){
    const y = Math.floor(loc/n);
    const x = loc%n;
    if(O < 3 && arr[y][x] === 'X'){
      arr[y][x] = 'O';
      ret = Math.max(ret, solve(loc, O+1));
      arr[y][x] = 'X';
    }
  }
  return ret;
}

if(solve(-1, 0)) console.log("YES");
else console.log("NO");

모든 경우의 수를 백트래킹으로 완전탐색해야 하는 문제였는데 N-Queen 문제처럼 1차원 배열 두개를 사용하여 최소 개수의 장애물 수를 구할 수 있을꺼란 근거 없는 생각을 해서 시간을 매우 낭비한 문제.

(상, 하), (좌, 우) 로 필요한 장애물 개수를 두 개의 1차원 배열에 저장한 후 하나로 합쳐 0이 아닌 개수를 세었는데 이 방법이 왜 맞을꺼라 확신했는지 의문이다.

아마도 대부분의 테스트케이스에서 계산이 통과해서였던 것 같다. 위 반례를 찾아낸 후에야 놓아줄 수 있었다.