[JS] 백준 15685번 : 드래곤 커브

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

15685번: 드래곤 커브

 

 

이 문제는 두 가지의 풀이방법을 이용했다.

1. 드래곤커브의 세대별 반복되는 규칙성을 이용

2. 드래곤 커브의 끝점과 지나온 경로를 계산식을 통해 다음 세대의 좌표를 구할 수 있음

 

 

 

 

 

 

 

 

📋풀이방법

1. 드래곤 커브는 세대에따라 좌표가 그려진다.

2. 이때 규칙이 생기는데 0 방향으로 했을 때의 규칙을 한번 아래에서 보자

0방향으로 시작했을 때

0 세대 - 0

1 세대 - 0 1

2 세대 - 0 1 2 1

3 세대 - 0 1 2 1 2 3 2 1

4 세대 - 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

1방향으로 시작했을 때

0 세대 - 1

1 세대 - 1 2

2 세대 - 1 2 3 2

3 세대 - 1 2 3 2 3 0 3 2

4 세대 - 1 2 3 2 3 0 3 2 3 0 1 0 3 0 3 2

3.위처럼 표현한 정보만으로도 규칙을 찾을 수 있다.

 -다음 세대는 이전 세대의 역방향으로 +1 한 방향을 나타내게 된다.

4. 또한 각 세대의 길이는 2의 제곱의 길이를 가진다

 - 0세대는 2의 0제곱 개의 수열을 가짐

 - 2세대는 2의 2제곱 개의 수열을 가짐

5. 이를 통해 0~10 세대의 드래곤 커브를 방향별로 미리 작성할 수 있다.

6. 그래서 주어진 드래곤 커브의 시작좌표와 방향과 세대를 가지고 미리만든 100 X 100 보드에 지나간 좌표를 체크해준다.

7. 미리 작성한 드래곤 커브 규칙으로 시작좌표에서 가야할 좌표를 증가 또는 감소 시켜주면된다.

8. 모든 지나온 경로를 확인하면서 정사각형으로 된 곳을 출력해준다.

 

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N]=input.shift().split(" ").map(Number);
let dragon=[];
for(var i=0;i<N;i++){
    dragon.push(input.shift().split(" ").map(Number));
}
let board = Array.from(Array(101), () => Array(101).fill(0));

let pattern = Array.from({length : 4},()=>Array(1024).fill(0));
pattern[0][0] = 0;
pattern[1][0] = 1;
pattern[2][0] = 2;
pattern[3][0] = 3;

// 드래곤 커브 셋팅
for (var k = 0; k < 4; k++) {
    for (var i = 1; i <= 10; i++) {
        
        let start = Math.pow(2, i - 1); 
        let end = Math.pow(2, i);
        //세대가 증가할 떄마다 공비가 2인 등비수열가 되는 것을 확인했다.
        //i세대는 2의 i제곱의 수열을 가지게 되고
        //다음 세대는 이전 세대의 역방향으로 +1 한 방향을 나타내게 된다.
        for (var j = start, l = start-1; j < end; j++, l--) {
            //다음세대의 j는 이전세대의 j-1에서 +1 한 것과 같다.
            pattern[k][j] = (pattern[k][l] +1) % 4
        }
    }
}
 // 드래곤 커브 그리기
dragon.forEach(v => {
    const [x, y, d, g] = v;
    var end = Math.pow(2, g);//g세대는 2^g까지의 방향갯수를 가지고 있다.

    var currX = x;
    var currY = y;
    board[currY][currX] = true;
    //미리 작성한 방향에따른 드래곤커브를 가지고 그 방향에따라 좌표값을 이동해준다.
    for (var j = 0; j < end; j++) { 
        if (pattern[d][j] == 0) {
            currX += 1;
        } else if (pattern[d][j] == 1) {
            currY -= 1;
        } else if (pattern[d][j] == 2) {
            currX -= 1;
        } else {
            currY += 1;
        }
        board[currY][currX] = true;//지나온 좌표들을 체크해준다.
    }
});

// 체크한 지나온 좌표들로 정사각형이 형성되는 부분을 찾는다.
var cnt = 0;
for (var i = 0; i < 100; i++) {
    for (var j = 0; j < 100; j++) {
        if (board[i][j] && board[i][j + 1] && board[i + 1][j] && board[i + 1][j + 1]) {
            cnt++;
        }
    }
}
console.log(cnt)

 

 

 

 

📋풀이방법

1. 주어진 드래곤 좌표를 하나씩 그려나간다.

2. 시작좌표부터 그리기 시작한다

3. 0세대부터 시작한다.

 -. 0세대에서 방향을 정한다.

 -. 다음 세대는 0세대에서 그린 방향을 기준으로 그려나가게된다.

 -. 이때 지나온 좌표들은 prev배열에 저장하고 100 X 100 맵에 지나왔다고 표시해준다.

7. 1세대 ~ 10세대는 아래와 같이 명령을 수행한다.

 - 지나온 좌표에서 끝점을 제외하고, 거꾸로 순회한다.

 - 지나온 좌표를 하나씩 아래의 공식에 따라 끝점의 좌표와 계산해준다.

  -> 새로 그려지는 좌표 Y =  지나온 경로X - 끝점X + 끝점Y

  -> 새로 그려지는 좌표 X =  - ( 지나온 경로Y - 끝점Y ) + 끝점X

 -이때 새로그려지는 좌표들도 지나온 경로 배열에 넣어준다.

 - 이를 이전 세대에서 저장한 지나온 좌표를 모두 순회할 때까지 수행한다.

8. 다음 세대를 모두 그렸다면 세대를 증가시켜준다.

9. 주어진 드래곤 커브를 모두 그렸다면 이제까지 체크해준 맵을 사각형으로 확인하면서 정사각형이 되는 부분의 갯수를 출력한다.

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N]=input.shift().split(" ").map(Number);
let dragon=[];
for(var i=0;i<N;i++){
    dragon.push(input.shift().split(" ").map(Number));
}
let board = Array.from(Array(101), () => Array(101).fill(0));
let answer = 0;
const dir = [
  [0, 1],  // x좌표가 증가하는 방향   (→) 
  [-1, 0],  // y좌표가 감소하는 방향 (↑) 
  [0, -1],  // x좌표가 감소하는 방향 (←) 
  [1, 0],   // y좌표가 증가하는 방향 (↓) 
]

// =>끝점을 기준으로 이전 좌표들을 시계방향으로 90도 회전


dragon.forEach(v => {
    const [x, y, d, g] = v; 
    board[y][x] = true; //정사각형이 형성되어있는 곳을 확인하기위해 시작좌표 true

    let currY = y;
    let currX = x;
    let currD = d;
    let currG = 0; //처음 세대는 0세대부터 시작한다.
    let prev = [[y, x]]; //주어진 세대까지 드래곤커브를 하기위해 지나온 경로를 저장함(처음 시작경로 저장)
    while (currG <= g) { //주어진 세대까지 반복
        //처음0세대일 때
        if (currG == 0) {
        currY += dir[currD][0]; //다음 좌표를 구한다.(0세대의 끝점)
        currX += dir[currD][1];
        prev.push([currY, currX]) //0세대의 끝점을 구하고 지나온 경로로 저장한다.
        board[currY][currX] = true; //지나갔다고 체크해준다.
        } //0세대 이후인 1~10세대 까지는 아래의 명령을 수행한다.
        else {
        const L = prev.length - 1; // 가장 마지막 좌표를 제외한다.
        for (let i = L - 1; i >= 0; i--) { //가장 마지막 좌표를 제외하고 시작 좌표까지 순회한다.
            const [prevY, prevX] = prev[i]; // 아래는 공식이다
            //새로 그려지는 좌표의 Y는 지나오 경로를 거꾸로 순회하면서(끝점을 제외한)
            //[ 지나온경로 X - 끝점 X + 끝점 Y ]이다.
            //새로 그려지는 좌표의 X는 
            //[  - (지나온 경로 Y - 끝점 Y ) + 끝점 X ]이다.
            //이는 방향에 상관없이 규칙적으로 가능하다.
            const newY = prevX - currX + currY; // 1 - 1 -1  ,     0 -1 -1
            const newX = -(prevY - currY) + currX; // -(0- -1) + 1  ,  -(0 - -1)+ 1 
            board[newY][newX] = true;
            prev.push([newY, newX]) //다음 세대를 그리기 위해 새로그려진 좌표는 지나온경로에 저장한다.
        }
        currY = prev[prev.length - 1][0]; // currG세대를 모두 그렸다면 끝점을 초기화해준다.
        currX = prev[prev.length - 1][1];
        }

        currG++; //다음세대로 증가한다.
    }
    })
    //체크한 좌표를 확인하면서 해당 좌표의 사각형모양에 모든 좌표가 체크 되어있는지 확인한다.
    for (let i = 0; i < 100; i++) {
    for (let j = 0; j < 100; j++) {
        if (board[i][j] && board[i + 1][j] && board[i][j + 1] && board[i + 1][j + 1]) {
        answer++;
        }
    }
}
console.log(answer)