[Node.js] 15685_드래곤 커브

문제

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

 

 

풀이

이 문제를 풀며 햇갈렸던 부분을 정리하겠다.

 

1. x와 y의 범위가 0부터 100 까지 이므로 생성해야할 2차원 배열을 101 X 101의 크기로 만들어야 한다.

2. 드래곤 커브는 끝지점을 기준으로 기존의 모양을 반시계로 돌린 모습이다.

그 과정에서 각 지점의 좌표를 구하는 것이 많이 어려웠다.

회전되는 새로운 점의 좌표는아래의 식과 같다.

const nY = prevX - curX + curY;
const nX = -(prevY - curY) + curX;

 

문제를 풀다보니 "반대인 오른쪽, 반시계방향으로 회전하면 어떤 식이 나올까?" 라는 생각이 들었다.

그래서 구해봤다.
const nY = prevX - curX + curX;
const nX = -(prevY - curY) + curY;

 

코드

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] = input.shift();
const dragons = input;
const map = Array.from({length: 101}, () => Array(101).fill(false));
const dir = [[1, 0], [0, -1], [-1, 0], [0, 1]];
let answer = 0;

dragons.forEach((e) => {
  const [x, y, direc, gen] = e;
  const arr = [[x, y]];
  let curX = x;
  let curY = y;
  for (let i = 0; i <= gen; i++) {
    if (i === 0) {
      const nX = x + dir[direc][0];
      const nY = y + dir[direc][1];
      map[y][x] = true;
      map[nY][nX] = true;
      arr.push([nX, nY]);
      curX = nX;
      curY = nY;
    }
    else {
      const len = arr.length - 1;
      for (let i = len - 1; i >= 0; i--){
        const [prevX, prevY] = arr[i];
        const nY = prevX - curX + curY;
        const nX = -(prevY - curY) + curX;
        arr.push([nX, nY]);
        map[nY][nX] = true;
      }
      curX = arr[arr.length - 1][0];
      curY = arr[arr.length - 1][1];
    }
  }
})

for (let i = 0; i < 100; i++){
  for (let j = 0; j < 100; j++){
    if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1]) {
      answer++;
    }
  }
}

console.log(answer)