[JavaScript] 백준 골드 4 : 3190 - 뱀

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

3190번: 뱀

---

📌 작성한 코드 

// 3190
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input[0]);
const K = Number(input[1]);

const apples = [];
for (let i = 2; i < 2 + K; i++) {
    apples.push(input[i].split(" ").map(Number));
}
const L = Number(input[2 + K]);

const rotates = [];
for (let i = 0; i < L; i++) {
    const [n, d] = input[K + 3 + i].split(" ");
    rotates.push([Number(n), d]);
}

const rotatePosition = rotates.map((v) => v[0]);
const board = Array.from({ length: N + 1 }, () => new Array(N + 1).fill(0));
apples.forEach(([x, y]) => (board[x][y] = 1));

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

let idx = 1;
let dir = 0;
let [x, y] = [1, 1];
board[x][y] = 2;

const queue = [];
queue.push([x, y]);

while (true) {
    // 1. 몸 길이 늘리기
    const nx = x + dx[dir];
    const ny = y + dy[dir];

    // 2. 부딪히면 끝남
    if (nx <= 0 || nx >= N + 1 || ny <= 0 || ny >= N + 1) break;
    if (board[nx][ny] === 2) break;

    if (board[nx][ny] === 0) {
        // 3. 사과 없으면
        board[nx][ny] = 2;
        const [tx, ty] = queue.shift();
        board[tx][ty] = 0;
    } else if (board[nx][ny] === 1) {
        // 4. 사과 있으면
        board[nx][ny] = 2;
    }

    const p = rotatePosition.indexOf(idx);
    if (p !== -1) {
        const d = rotates[p][1];

        if (d === "D") {
            dir = (dir + 1) % 4;
        } else {
            dir = (4 + dir - 1) % 4;
        }
    }

    queue.push([nx, ny]);
    x = nx;
    y = ny;
    idx++;
}

console.log(idx);

 

📌 설명 

뱀은 매 초마다 이동하는데 다음과 같은 규칙을 따라 이동한다. 

(1) 뱀은 몸 길이를 늘려서 앞의 칸에 머리를 위치시킨다.
(2) 벽이나 몸에 부딪히면 게임이 끝난다.
(3) 이동한 칸에 사과가 있다면, 사과는 사라지고 꼬리는 그대로 둔다.
(4) 이동한 칸에 사과가 없다면, 몸 길이를 줄여서 꼬리 한 칸을 없앤다. 

 

(0) 초기 세팅하기

- 사과의 위치 : `apples`

- 회전할 시간과 방향 : `rotates`

- 뱀이 이동할 N * N 보드 : `board` / 좌표가 0인 부분을 사용하기 않고 1부터 N까지의 인덱스를 사용하기 위해서 (N+1) * (N+1)로 선언하였다.

- 회전 시간만 저장하기 위한 : `rotatePosition`

 

- 시간을 기록할 변수 : `idx`

- 뱀의 몸이 존재하는 위치를 저장할 큐 : `queue`

- 뱀의 머리가 존재하는 위치 : `[x, y]`

- 뱀의 머리가 향하고 있는 방향 : `dir`

let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input[0]);
const K = Number(input[1]);

const apples = [];
for (let i = 2; i < 2 + K; i++) {
    apples.push(input[i].split(" ").map(Number));
}
const L = Number(input[2 + K]);

const rotates = [];
for (let i = 0; i < L; i++) {
    const [n, d] = input[K + 3 + i].split(" ");
    rotates.push([Number(n), d]);
}

const rotatePosition = rotates.map((v) => v[0]);
const board = Array.from({ length: N + 1 }, () => new Array(N + 1).fill(0));
apples.forEach(([x, y]) => (board[x][y] = 1));

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

let idx = 1;
let dir = 0;
let [x, y] = [1, 1];
board[x][y] = 2;

const queue = [];
queue.push([x, y]);

 

(1) 뱀 몸 길이 늘리기 

- 뱀이 바라보고 있는 방향에서 한 칸 앞의 좌표를 구한다. (nx, ny) 

// 1. 몸 길이 늘리기
const nx = x + dx[dir];
const ny = y + dy[dir];

(2) 몸이나 벽에 부딪히면 게임 종료 

- (1)에서 이동한 위치가 벽에 부딪히거나, 뱀의 몸통에 부딪힌다면 게임을 종료한다.(반복문을 탈출한다.)

// 2. 부딪히면 끝남
if (nx <= 0 || nx >= N + 1 || ny <= 0 || ny >= N + 1) break;
if (board[nx][ny] === 2) break;

(3) 사과가 없으면, 꼬리를 줄이기 

- 뱀의 길이를 증가시킬 때마다 큐에 뱀의 위치를 저장하고, 꼬리를 줄여야 하는 상황에서 큐의 맨 앞에 저장된 위치를 제거하면 쉽게 꼬리를 제거할 수 있다.

if (board[nx][ny] === 0) {
        // 3. 사과 없으면
        board[nx][ny] = 2;
        const [tx, ty] = queue.shift(); // 저장해둔 뱀 몸통에서 맨 첫번째(꼬리) 위치 가져오기
        board[tx][ty] = 0; // 제거
    }

(4) 사과가 있다면, 뱀 그대로 두기

else if (board[nx][ny] === 1) {
        // 4. 사과 있으면
        board[nx][ny] = 2;
    }

(5) 뱀 머리 회전하기 

- rotates에는 회전해야 하는 시간과 방향이 저장되어 있다. 그래서 rotatePosition에 현재 시간이 해당 된다면 뱀의 머리를 회전 시켜야 한다.

- 방향이 D라면 오른쪽으로 회전해야 하기 때문에 `방향 + 1`을 해주고, 방향이 L이라면 왼쪽으로 회전해야 하기 떄문에 `방향 - 1`을 해준다.

- 방향 + 1/ -1을 하면서 배열의 범위를 벗어날 수 있기 때문에 4를 더해주고 4로 나눈 나머지 값을 사용한다.

const p = rotatePosition.indexOf(idx);
if (p !== -1) {
    const d = rotates[p][1];

    if (d === "D") {
        dir = (dir + 1) % 4;
    } else {
        dir = (4 + dir - 1) % 4;
    }
}

(6) 업데이트하기 

- 새로 생겨난 몸통, 뱀의 머리 위치, 시간을 업데이트 해준다.

queue.push([nx, ny]);
x = nx;
y = ny;
idx++;

 

✅ 성공