[JavaScript] 백준 14503 로봇 청소기 (JS)

로봇 청소기

📚 문제 설명

N * M 크기의 방이 있다. 이 방은 벽(1)과, 빈 방(0)으로 이루어져 있고, 범위 바깥은 전부 벽으로 이루어져 있다.
빈방은 전부 청소가 되어있지 않다고 할 때, 로봇 청소기가 청소를 진행한 칸은 몇칸인지 구하여라.

로봇 청소기는 아래와 같이 움직인다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우,
   2 - 1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2 - 3. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있는 경우,
   3 - 1. 반시계 방향으로 $90^\circ$ 회전한다.
   3 - 2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3 - 3. 1번으로 돌아간다.

👨🏻‍💻 풀이 과정

우선 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라 보고 있다고 문제에 나와 있기 때문에 이 숫자 순서대로 방향 배열 dx, dy를 만들어 주었다.
그 이후로는 위의 청소기 움직임을 종료 조건이 충족되기 전까지 반복되도록 만들면 된다.

메인 로직

• 현재 위치 청소
• 회전 후, 정면에 0인 방이 있으면 이동.
• 주변에 0인 방이 없다면, 뒤로 이동.
• 뒤로 이동 중 벽과 만나면 종료.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const [N, M] = input.shift().split(' ').map(Number);
    let [nowX, nowY, direction] = input.shift().split(' ').map(Number);

    const MAP = input.map(v => v.split(' ').map(Number));
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];

    // 벽이 아니고, 청소 가능한지 확인.
    const isCleanable = (x, y) => x >= 0 && x < N && y >= 0 && y < M && MAP[x][y] === 0;

    // 회전 후 이동.
    const rotateAndMove = () => {
        // 4방향으로 회전하며 이동
        for (let i = 1; i <= 4; i++) {
            // 반시계 방향으로 이동.
            const nextDirection = (direction + 4 - i) % 4;
            const [x, y] = [nowX + dx[nextDirection], nowY + dy[nextDirection]];
            // 회전 후, 청소 해야하는 구역이 정면에 있다면, 이동.
            if (isCleanable(x, y)) {
                [nowX, nowY, direction] = [x, y, nextDirection];
                return true;
            }
        }

        return false;
    };

    const cleanRoom = () => {
        let cnt = 0;

        while (true) {
            // 현재 위치 청소.
            if (MAP[nowX][nowY] === 0) {
                MAP[nowX][nowY] = 2;
                cnt++;
            }

            // 회전 후 청소 해야하는지 확인.
            // 만약 청소할 구역이 없다면, 뒤로 이동.
            if (!rotateAndMove()) {
                const backwardDirection = (direction + 2) % 4;
                const [x, y] = [nowX + dx[backwardDirection], nowY + dy[backwardDirection]];
                // 만약 뒤로 이동했을 때 벽과 만난다면 종료
                if (x >= 0 && x < N && y >= 0 && y < M && MAP[x][y] !== 1) {
                    [nowX, nowY] = [x, y];
                } else {
                    break;
                }
            }
        }

        console.log(cnt);
    };

    cleanRoom();

🧐 후기

처음에 작성한 풀이가 시간 복잡도가 너무 크게 구성되어져 있어서 계속 통과를 못해서 결국 첫번째 풀이를 아예 전부 다 지우고 다시 작성한 후에 통과할 수 있었다.
첫번째 풀이도 전체적인 로직 자체는 이 풀이와 동일하지만 4방향을 굳이 한번 다 확인하고 만약 0인 방을 발견하면, 다시 회전을 진행하기 때문에 불필요한 로직이 더 들어가 있고, 방향 배열인 dx와 dy를 위와 같이 이 문제와 같게 0번일 경우 북쪽... 이런식으로 작성을 하지 않아서 불필요한 가정문도 많이 들어가 있었기 때문에 통과하지 못한 것 같다.