(JS) 백준 3190번 : 뱀 (큐와 데크)

3190번: 뱀

문제를 풀기위해 마래와 같은 요소들을 고려하였다.

1. 뱀의 머리 위치에 따라 뱀의 길이가 증가하거나 게임이 종료되므로 queue의 형태로 뱀 배열을 관리했다.
2. readline과 join을 통해 하나의 문자열로 입력되는 값을 처리하기 위해 split, slice, reduce, map등을 활용했다.
3. 뱀의 이동에는 enqueue와 dequeue가 사용되었다.
4. 경과한 시간 변수를 관리하고 이를 방향전환 정보와 매칭해서 사용했으며 방향은 상하좌우 배열로 따로 관리했다.

const readline = require("readline");

const solution = (data) => {
    let boardSize = Number(data.split("\n")[0]);
    let board = Array.from({ length: boardSize }, () => Array(boardSize).fill(0));
    let appleSize = Number(data.split("\n")[1]);
    let apple = data.split("\n").slice(2, 2 + appleSize);

    apple.forEach((val) => {
        let [x, y] = val.split(" ");
        board[Number(x) - 1][Number(y) - 1] = 1;
    });

    let changeDir = data
        .split("\n")
        .slice(3 + appleSize)
        .reduce((acc, line) => {
            const [key, value] = line.split(" ");
            acc[key] = value;
            return acc;
        }, {});

    let direction = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
    ];
    let nowDir = 0;
    let snake = [[0, 0]];
    let time = 0;

    const isWall = (head) => {
        if (head[0] >= boardSize || head[1] >= boardSize) return true;
        if (head[0] < 0 || head[1] < 0) return true;
        return false;
    };

    const isSelf = (head) => {
        return snake.some((val) => val[0] === head[0] && val[1] === head[1]);
    };

    const isApple = (head) => {
        if (board[head[0]][head[1]] === 1) {
            board[head[0]][head[1]] = 0;
            return true;
        }
        return false;
    };

    const move = (head) => {
        if (time in changeDir) {
            if (changeDir[time] === "D") {
                if (nowDir === 3) nowDir = 0;
                else nowDir++;
            } else if (changeDir[time] === "L") {
                if (nowDir === 0) nowDir = 3;
                else nowDir--;
            }
        }
        let [x, y] = head;
        return [x + direction[nowDir][0], y + direction[nowDir][1]];
    };

    while (1) {
        let nowHead = snake[snake.length - 1];
        let newHead = move(nowHead);
        time++;
        if (isWall(newHead) || isSelf(newHead)) break;
        if (isApple(newHead) === false) snake.shift();
        snake.push(newHead);
    }

    return time;
};

const input = [];
readline
    .createInterface({
        input: process.stdin,
        output: process.stdout,
    })
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        const data = input.join("\n");
        console.log(solution(data));
    });

 

 

 

1. queue의 형태로 뱀 배열 관리

이 문제에서는 현재 뱀 머리의 위치가 매우 중요하다. 뱀 머리의 위치로 계산해야 할 것들은 아래와 같다.

• 뱀이 보드 밖으로 나감
  뱀의 머리가 보드 바깥으로 나간경우 게임이 종료된다.
• 뱀이 자신의 몸통에 부딫힘
  뱀의 머리가 자신의 몸통에 부딪힌경우 게임이 종료된다.
• 사과를 먹음
  뱀의 머리 위치에 사과가 존재할경우 사과가 없어지고 꼬리가 길어진다.

사실상 이 조건들만 제대로 구현하면 문제의 내용을 모두 구현한것과 다름없다.

뱀이 차지하는 좌표를 담고있는 배열 snake를 만들고 배열의 마지막값을 머리로 사용했다.

처음 시작 시 뱀은 0,0의 좌표 한칸을 차지하고 있으므로 배열의 초기값은 [[0, 0]] 이다.

 

 

 

2. 문자열 처리

백준의 입력값은 표준입력으로 들어온다. 이를 직접 처리해주어야 하는데 이 문제에서는 입력값을 모두 문자열로 만들어 함수에 전달했다. 이를 처리하기위해 split과 map, slice, reduce 등을 사용했다.

let boardSize = Number(data.split("\n")[0]);
    let board = Array.from({ length: boardSize }, () => Array(boardSize).fill(0));
    let appleSize = Number(data.split("\n")[1]);
    let apple = data.split("\n").slice(2, 2 + appleSize);

apple.forEach((val) => {
    let [x, y] = val.split(" ");
    board[Number(x) - 1][Number(y) - 1] = 1;
});

let changeDir = data
    .split("\n")
    .slice(3 + appleSize)
    .reduce((acc, line) => {
        const [key, value] = line.split(" ");
        acc[key] = value;
        return acc;
    }, {});

 

• board : 2차원 배열로 보드의 내용이 저장된다. 보드 사이즈에 따라 0으로 이루어진 배열을 만들고 사과가 있는 위치에 1을 집어넣었다.
• apple : 사과의 좌표가 저장된다. 개수에따라 입력 내용물의 길이도 달라지므로 appleSize를 따로 빼서 사용했다.
• changeDir : 방향전환에 대한 정보를 저장했다. 방향을 전환할 시간을 key, 전환할 방향을 value로 둔 객체를 생성해서 사용했다.

 

3. 뱀 전체의 이동

뱀을 이동시키는것은 모든 배열의 값을 변화시켜야한다고 생각할 수 있다. 하지만 문제의 조건에따라 보다 간단히 구현할 수 있다.

• 이동 방향에 사과가 존재하는경우 (enqueue만 실행)
  사과가 존재하면 꼬리가 한칸 길어진다. 이동과 동시에 꼬리가 길어진다는 것은 이동방향으로 머리 하나만 추가하면 된다.
• 이동 방향에 사과가 존재하지 않는 경우 (enqueue와 dequeue 둘다 실행)
  이동방향으로 머리를 추가하고 꼬리를 하나 제거하면 된다. 몸통은 결국 머리가 있던 방향으로 가기 때문에 기존 뱀의 좌표 전체가 이동후의 몸통으로 대체된다고 생각하면 좋다.

 

 

4. 시간 변수와 방향 변환

time이라는 변수를 두어 뱀이 한번 이동할때마다 1씩 더해줬다. 이는 연산이 끝난뒤 최종 정답으로 활용이 되고 방향을 전환할 시간을 매칭할때도 사용된다.

const move = (head) => {
    if (time in changeDir) {
        if (changeDir[time] === "D") {
            if (nowDir === 3) nowDir = 0;
            else nowDir++;
        } else if (changeDir[time] === "L") {
            if (nowDir === 0) nowDir = 3;
            else nowDir--;
        }
    }
    let [x, y] = head;
    return [x + direction[nowDir][0], y + direction[nowDir][1]];
};

 

현재 경과한 시간과 방향을 변화시켜야 할 시간을 매칭시킨다. 객체에 key형태로 시간값이 저장되어있으므로 in 연산자를 통해 방향 변화의 유무를 확인했다.

방향을 변화시켜야 한다면 D 혹은 L에 따라 nowDir값을 변경했다. nowDir은 direction배열로 연결되므로 방향 설정을 간편하게 할 수 있다.

 

 

 

※ 코드 개선 방향

1. 문자열 데이터 파싱 최소화

문자열 데이터를 처리하기 위해 split, slice, reduce, map을 여러번 사용했는데 이를 간소화 시킬 수 있을 것이다.

• 전달 데이터를 문자열이 아닌 배열 자체로 전달해서 더욱 편리하게 사용한다.
• 전달 받은 문자열 데이터를 "\n" 기준으로 한번 split 하여 배열에 모두 저장한다. 이후 데이터에 접근할때는 배열 인덱스로 접근하여 간단하게 사용이 가능하다.

 

2. isApple 함수 간소화

true, false를 간단한 조건에 따라 반환하는 함수는 간소화 시키기 좋다.

 

• 변경 전

const isApple = (head) => {
    if (board[head[0]][head[1]] === 1) {
        board[head[0]][head[1]] = 0;
        return true;
    }
    return false;
};

 

• 변경 후

const isApple = (head) => board[head[0]][head[1]] === 1 && !(board[head[0]][head[1]] = 0);

 

 

3. 기타 개선

• shift는 시간복잡도가 O(n)인 dequeue 방식이다. 시간복잡도가 O(1)인 dequeue를 사용하기 위해서는 queue를 직접 구현해야한다. 복잡한 로직에서는 직접 구현하는것이 좋을 수 있다.
• move함수의 조건문을 간소화하거나 isWall, isSelf 함수의 내용을 합쳐서 처리할 수 도 있다.