[Node.js] 15684_사다리

문제

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

 

 

풀이

해당 문제는 dfs를 이용해 풀이했으며 문제의 조건을 구현하는데 조금 어려움이 있었다.

 

검증하고 있는 칸에 사다리를 놓을 수 있는지 검증하는 로직에서 이중으로 쓸대없이 검증을 진행했어서 시간초과 에러가 발생했었다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e.split(' ').map(Number));

const [n, m, h] = input.shift();
const ladder = input;
const map = Array.from(Array(h + 1), () => Array(n + 1).fill(false));
let answer = Infinity;

ladder.forEach(([y, x]) => {
  map[y][x] = true;
});

const movingCheck = () => {
  for (let i = 1; i <= n; i++){
    let cur = i;
    for (let j = 1; j <= h; j++){
      if (map[j][cur] === true) cur++;
      else if (map[j][cur-1] === true) cur--;
    }
    if (cur !== i) return false;
  }
  return true;
}

const dfs = (line, depth) => {
  if (depth > 3) {
    return;
  }
  if (movingCheck()) {
    if (depth < answer) answer = depth;
    return;
  }
  for (let i = line; i <= h; i++) {
    for (let j = 1; j < n; j++) {
      if (map[i][j] || map[i][j - 1] || map[i][j + 1]) continue;
      map[i][j] = true;
      dfs(i, depth + 1);
      map[i][j] = false;
    }
  }
};
dfs(1, 0);

console.log(answer === Infinity ? -1 : answer);