(javascript) 블록 이동하기

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

 

 문제를 굳이 분류하자면 구현 문제라고 생각한다.

 로봇이 x, y 한칸만 차지하는게 아니라 두 칸을 차지하면서 회전시에 추가로 장애물을 검사해줘야 해서 단순한 bfs는 아니었다.

첫번째 구현

 먼저 로봇의 위치를 표현하기 위한 형태를 정해야했다.

 처음에는 로봇의 위치를 (x, y, dir) 세개의 값으로 정했다. x는 x좌표, y는 y좌표, dir는 로봇의 방향이다. dir이 0이면 가로방향, dir이 1이면 세로 방향이다.

 

 기본적으로는 bfs를 적용한다.

 로봇의 위치를 queue에 넣으면서 bfs를 진행한다.

 로봇의 현재 위치를 queue에서 꺼낸 뒤, 다음에 로봇이 갈 수 있는 모든 위치를 검사하고 다시 queue에 넣는다.

 

 이 때, 로봇이 갈 수 있는 모든 위치를 구하는 과정을 구현하는게 복잡했다.

 

 1. 로봇은 상하좌우로 이동할 수 있다. 이 때 로봇의 방향은 바뀌지 않는다.

 이 과정은 비교적 쉽게 구할 수 있다.

 

 2. 로봇은 4가지 방법으로 회전할 수 있다. 이 때 장애물 검사를 해야한다.

 이 과정이 꽤나 머리 아프다.

 처음에 구현한 방법은, 현재 로봇의 방향(dir)에 따라서 로봇이 회전할 수 있는 모든 경우의 수(8가지)를 일일이 계산하는 것이었다.

 모든 경우에 로봇이 회전할 수 있는지 검사하고, 회전을 막는 장애물이 있는지 검사한다.

 

 이 방법으로 구현해서 제출했을 때 일부는 성공했지만 일부는 실패했다.

 사실 문제는 구현방법이 아니라 사소한 실수였지만, 제출한 코드를 수정하려고 보니 코드가 너무 깔끔하지 못했다.

 그래서 좀 더 다듬기로 했다.

두번째 구현

 로봇의 위치를 표현하는 방법을 바꾸기로 했다.

 로봇의 위치를 (x, y, vx, vy) 네개의 값으로 표현하기로 했다. x, y는 로봇의 위치, vx, vy는 로봇의 방향을 (vx, vy)벡터로 표현한 것이다.

 

 로봇의 방향을 벡터로 표현함으로써 회전변환행렬을 정할 수 있게 됐다.

https://ko.wikipedia.org/wiki/%ED%9A%8C%EC%A0%84%EB%B3%80%ED%99%98%ED%96%89%EB%A0%AC

회전변환행렬 - 위키백과, 우리 모두의 백과사전

 로봇이 시계방향으로 회전하면 로봇의 방향 벡터는 (-vy, vx)로 변환된다. 반시계방향으로 회전하면 로봇의 방향 벡터는 (vy, -vx)가 된다.

 이 두개의 벡터를 각각 (cwx, cwy)와 (ccx, ccy)로 저장한다. (cw : clockwise, cc: counter-clockwise)

 그리고 변환된 벡터의 각 요소가 음수값을 가지게 될 경우를 생각해 벡터의 요소를 양수로 변환하는 함수를 만들었다.(transform)

 check함수는 주어진 (x, y), (vx, vy)에 로봇을 놓을 수 있는지 검사하는 함수이다.

 

 이렇게 구현함으로써 8가지 경우의 수를 각각 검사하는 대신 4개의 경우의 수만 검사하게 되었다.

 (x, y) -> (cwx, cwy)

 (x, y) -> (ccx, ccy)

 (x+vx, y+vy) -> (cwx, cwy)

 (x+vx, y+vy) -> (ccx, ccy)

 

코드

function solution(board) {
    var answer = 0;
    const N = board.length;
    const visited = Array.from({ length: N }, () => Array.from({ length: N }, () => Array(2).fill(false)));

    var queue = Array(); // [x, y, vx, vy, count]
    queue.push([0, 0, 1, 0, 0]);
    visited[0][0][1] = true;

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

    // (_x, _y)에서 (_vx, _vy)로 로봇을 놓을 수 있는지 검사하는 함수
    const check = (_x, _y, _vx, _vy) => {
        if (_x < 0 || _x >= N) return false;
        if (_y < 0 || _y >= N) return false;
        if (_x + _vx < 0 || _x + _vx >= N) return false;
        if (_y + _vy < 0 || _y + _vy >= N) return false;
        if (board[_y][_x] === 1 || board[_y + _vy][_x + _vx] === 1) return false;
        if (visited[_x][_y][_vx]) return false;
        return true;
    }

    // vx, vy가 항상 양수가 되도록 변환해주는 함수
    const transform = (_x, _y, _vx, _vy) => {
        return [
            _vx < 0 ? _x + _vx : _x,
            _vy < 0 ? _y + _vy : _y,
            _vx < 0 ? -_vx : _vx,
            _vy < 0 ? -_vy : _vy
        ];
    }

    // bfs
    while (queue.length > 0) {
        var [x, y, vx, vy, count] = queue.shift();
        // console.log(`current : (${x}, ${y}) / (${vx}, ${vy})`);
        // 종료조건
        if (x === N - 2 && y === N - 1 && vx === 1) {
            return count;
        }
        if (x === N - 1 && y === N - 2 && vx === 0) {
            return count;
        }
        // 다음 탐색할 칸
        // 상하좌우
        for (var i = 0; i < 4; i++) {
            if (check(x + dx[i], y + dy[i], vx, vy)) {
                queue.push([x + dx[i], y + dy[i], vx, vy, count + 1]);
                visited[x + dx[i]][y + dy[i]][vx] = true;
            }
        }
        // 회전
        // (vx, vy)를 시계방향 회전 -> (-vy, vx)
        // (vx, vy)를 반시계방향 회전 -> (vy, -vx)
        var [cwx, cwy] = [-vy, vx];
        var [ccx, ccy] = [vy, -vx];
        // 진행방향 오른쪽
        while (true) {
            // 장애물 검사가 범위 안에 있는지 확인
            if (x + cwx < 0 || x + cwx >= N) break;
            if (y + cwy < 0 || y + cwy >= N) break;
            // 장애물 검사
            if (board[y + vy + cwy][x + vx + cwx] !== 1) {
                // vx, vy가 양수가 되도록 변환
                var [_x, _y, _vx, _vy] = transform(x, y, cwx, cwy);
                // 이동 가능한지 검사
                if (check(_x, _y, _vx, _vy)) {
                    queue.push([_x, _y, _vx, _vy, count + 1]);
                    visited[_x][_y][_vx] = true;
                }
            }
            if (board[y + cwy][x + cwx] !== 1) {
                var [_x, _y, _vx, _vy] = transform(x + vx, y + vy, cwx, cwy);
                if (check(_x, _y, _vx, _vy)) {
                    queue.push([_x, _y, _vx, _vy, count + 1]);
                    visited[_x][_y][_vx] = true;
                }
            }
            break;
        }
        // 진행방향 왼쪽
        while (true) {
            if (x + ccx < 0 || x + ccx >= N) break;
            if (y + ccy < 0 || y + ccy >= N) break;
            if (board[y + vy + ccy][x + vx + ccx] !== 1) {
                var [_x, _y, _vx, _vy] = transform(x, y, ccx, ccy);
                if (check(_x, _y, _vx, _vy)) {
                    queue.push([_x, _y, _vx, _vy, count + 1]);
                    visited[_x][_y][_vx] = true;
                }
            }
            if (board[y + ccy][x + ccx] !== 1) {
                var [_x, _y, _vx, _vy] = transform(x + vx, y + vy, ccx, ccy);
                if (check(_x, _y, _vx, _vy)) {
                    queue.push([_x, _y, _vx, _vy, count + 1]);
                    visited[_x][_y][_vx] = true;
                }
            }
            break;
        }
    }
    return answer;
}

 

후기

 사실 첫번째 구현도 전체적인 방향은 틀리지 않았지만, 다른 실수때문에 오답이 나오는 것이었다.

 (x, y)좌표에 장애물이 있는지 검사하려면 board에서 (x, y)좌표를 검사해야하는데, board[x][y]에 접근하려는게 문제였다.

 입력되는 board는 가로가 x, 세로가 y이기 때문에 (x, y)좌표를 검사하려면 board[y][x]에 접근해야한다.

 

 2차원 배열에서 x, y값이 뒤바뀌는 실수는 종종 나올 수 있다. 앞으로는 유의해야겠다.