[백준] 15685 드래곤 커브 (Javascript)

문제

BOJ15685_드래곤 커브

문제 이해

처음엔 아래의 그림처럼 네 개의 선분이 정사각형을 이루고 있는 정사각형의 개수를 구하는 문제라고 잘못 이해했다.

선분으로 이어져있는지 판별하려면 구현이 좀 더 복잡해지기 때문에 살짝 막막했다.

하지만 문제를 자세히 읽어보면 네 꼭짓점이 모두 드래곤 커브의 "일부"인 정사각형의 개수를 구하는 프로그램을 작성하라고 적혀있다.

이 말은 즉, 아래 그림처럼 정사각형의 네 꼭짓점이 드래곤 커브에 포함되어있기만 하면 개수가 인정되는 것이다.

접근법

기본 세팅

• 드래곤 커브의 시작 좌표인 $x$와 $y$는 $0$이상 $100$이하의 값을 갖는다. 따라서 $0$과 $100$을 포함해야되기 때문에 $100 \times 100$이 아니라 $101 \times 101$크기의 좌표평면을 만들고 $0$으로 채워준다. 추후에 드래곤 커브의 이동 경로에 포함된 칸의 원소를 $0$에서 $1$로 바꿔줄 것이다.

const map = Array.from(Array(101), () => Array(101).fill(0));

• 각각의 드래곤 커브에는 시작 방향($d$)가 주어진다. 따라서 $d$에 따라 방향을 달리하기 위해 dir 변수를 만든다.

const dir = {
  0: [1, 0],
  1: [0, -1],
  2: [-1, 0],
  3: [0, 1],
};

dragoncurve()

• 하나의 드래곤 커브를 처리할 함수 dragoncurve(x,y,d,g)를 정의한다. 해당 함수는 드래곤 커브의 시작위치($x,y$), 시작 방향($d$), 세대($g$)를 매개변수로 전달받는다.
• 시작 위치($x,y$)는 무조건 드래곤 커브에 포함되기 때문에 방문처리 해준다.

map[y][x] = 1;

• 이동 경로를 담을 변수 order를 선언하고, 처음엔 시작 방향($d$)을 담아준다.

let order = [dir[d]];

• 각각의 세대는 이전 세대의 이동 방향을 시계방향으로 $90$도 회전시킨 뒤 이를 역방향으로 수행한다.
  • 이동 방향을 $90$도 회전시키는 작업은 rotate()라는 함수로 분리한다.
  • 다음 세대에서 역방향으로 수행하기 위해서는 order에 담긴 원소를 pop()하여 마지막 원소부터 꺼내주면 된다. 그리고 newOrder라는 변수를 선언한 뒤 order에서 pop()한 데이터를 newOrder에 push()한다. 이때 그냥 push()하는 것이 아니라 rotate()함수로 $90$도 회전시킨 방향을 push()한다. 그 후 다음 세대가 되면 newOrder에 담긴 원소를 order에 할당해주면 된다.

for (let i = 0; i <= g; i++) {
  while (order.length) {
    const [dx, dy] = order.pop();
    x += dx;
    y += dy;
    if (y <= 100 && x <= 100 && y >= 0 && x >= 0) map[y][x] = 1;
    newOrder.push(rotate(dx, dy));
  }
  order = newOrder.map((e) => [...e]); // 깊은 복사
}

또한 $x,y$가 범위를 벗어날 경우 에러를 발생시킬 수 있기 때문에 if (y <= 100 && x <= 100 && y >= 0 && x >= 0)조건문을 추가하여 제한을 걸어둔다.
(해당 조건문 없이 제출했을 때도 통과하긴 했지만, 입력값이 100 100 3 0이 주어졌을 때 해당 조건문이 없으면 에러가 발생한다.)

rotate()

• rotate(x,y)함수는 이동 방향($dx, dy$)를 인수로 전달받아서 시계방향으로 90도 회전한 이동 방향을 리턴한다.
  

function rotate(x, y) {
    // [+1, 0] -> [0, +1]
    // [0, +1] -> [-1, 0]
    // [-1, 0] -> [0, -1]
    // [0, -1] -> [+1, 0]
    if (x !== 0) return [0, -x];
    else if (y !== 0) return [y, 0];
}

countRect()

• countRect()함수는 map을 순회하며 사각형의 개수를 카운트한다.

function countRect() {
  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++;
    }
  }
}

전체 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let N;
let curve = [];

rl.on('line', (line) => {
    if (!N) N = +line;
    else curve.push(line.split(' ').map(Number));
    if (curve.length === N) rl.close();
}).on('close', () => {
    console.log(solution());
});

function solution() {
    let answer = 0;
    const map = Array.from(Array(101), () => Array(101).fill(0));
    const dir = {
        0: [1, 0],
        1: [0, -1],
        2: [-1, 0],
        3: [0, 1],
    };

    for (let [x, y, d, g] of curve) {
        dragonCurve(x, y, d, g);
    }

    countRect();

    return answer;

    function dragonCurve(x, y, d, g) {
        map[y][x] = 1;
        let order = [dir[d]];
        let newOrder = [];
        for (let i = 0; i <= g; i++) {
            while (order.length) {
                const [dx, dy] = order.pop();
                x += dx;
                y += dy;
                if (y <= 100 && x <= 100 && y >= 0 && x >= 0) map[y][x] = 1;
                newOrder.push(rotate(dx, dy));
            }
            order = newOrder.map((e) => [...e]);
        }
    }

    function countRect() {
        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++;
            }
        }
    }
}

function rotate(x, y) {
    // [+1, 0] -> [0, +1]
    // [0, +1] -> [-1, 0]
    // [-1, 0] -> [0, -1]
    // [0, -1] -> [+1, 0]
    if (x !== 0) return [0, -x];
    else if (y !== 0) return [y, 0];
}

코드 개선(rotate제거)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let N;
let curve = [];

rl.on('line', (line) => {
    if (!N) N = +line;
    else curve.push(line.split(' ').map(Number));
    if (curve.length === N) rl.close();
}).on('close', () => {
    console.log(solution());
});

function solution() {
    let answer = 0;
    const map = Array.from(Array(101), () => Array(101).fill(0));
    const dir = {
        0: [1, 0],
        1: [0, -1],
        2: [-1, 0],
        3: [0, 1],
    };

    for (let [x, y, d, g] of curve) {
        dragonCurve(x, y, d, g);
    }

    countRect();

    return answer;

    function dragonCurve(x, y, d, g) {
        map[y][x] = 1;
        let order = [d];
        let newOrder = [];
        for (let i = 0; i <= g; i++) {
            for (let j = order.length - 1; j >= 0; j--) {
                const [dx, dy] = dir[order[j]];
                x += dx;
                y += dy;
                if (y <= 100 && x <= 100 && y >= 0 && x >= 0) map[y][x] = 1;
                newOrder.push((order[j] + 1) % 4);
            }
            order = [...newOrder];
        }
    }

    function countRect() {
        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++;
            }
        }
    }
}

rotate()함수를 제거하는 대신 order에는 방향을 넣어주고 시계방향 회전을 newOrder.push((order[j] + 1) % 4);로 처리했다.