[Node.js] 16235_나무 재테크

문제

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

 

 

풀이

이 문제는 구현 난이도는 그저 그랬으나 시간 복잡도를 신경써야 하는 문제였다.

 

기존 코드에서는 죽은 나무들을 담는 큐를 만들어 계산했지만, 이런 방식으로 풀이하면 시간 초과가 발생하므로 기존 나무를 담는 배열에 각 나무의 죽음 여부를 나타내는 값을 하나 추가하고 이를 활용해 풀이했다.

추가적으로 내가 실수하며 풀이 시간이 40분 정도 증가했는데, 문제에서 입력으로 들어오는 X, Y 개념을 잘못 이해했다. 나는 좌표평면에서 세로를 Y, 가로를 X로 생각했다. 하지만 문제에서는 상단에서 떨어진 정도를 X, 맨 좌측에서 떨어진 정도를 Y로 표기했다. 이를 반대로 사용해 각 땅에 줘야하는 양분을 잘못 전달했었다.

 

코드

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, k] = input.shift();
let plusHp = input.splice(0, n);
let trees = input.map(e => [...e, 0]);
let map = Array.from(Array(n), () => Array(n).fill(5));
const dir = [
  [-1, -1], [0, -1], [1, -1], [1, 0],
  [1, 1], [0, 1], [-1, 1], [-1, 0]
];

const spring = () => {
  trees = trees.sort((a, b) => a[2] - b[2]);
  for (let i = 0; i < trees.length; i++){
    const [x, y, age] = trees[i];
    if (map[x - 1][y - 1] >= age) {
      map[x - 1][y - 1] -= age;
      trees[i][2] += 1;
    }
    else {
      trees[i][3] = -1;
    }
  }
  
}

const summer = () => {
  trees = trees.filter(e => {
    if (e[3] === 0) return true;
    else {
      const [x, y, age, _] = e;
      map[x - 1][y - 1] += Math.floor(age / 2);
      return false;
    }
  });
}

const automn = () => {
  trees.forEach(e => {
    const [x, y, age, _] = e;
    if (age % 5 === 0) {
      for (let i = 0; i < 8; i++) {
        const nY = y - 1 + dir[i][1];
        const nX = x - 1 + dir[i][0];
        if (nY >= 0 && nY < n && nX >= 0 && nX < n) {
          trees.push([nX + 1, nY + 1, 1, 0]);
        }
      }
    }
  })
}

const winter = () => {
  for (let i = 0; i < n; i++){
    for (let j = 0; j < n; j++){
      map[i][j] += plusHp[i][j];
    }
  }
}

for (let i = 0; i < k; i++){
  spring();
  summer();
  automn();
  winter();
}
console.log(trees.length);