1726 로봇 (자바스크립트)

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

===

문제 분석

로봇이 현재 위치에서 할 수 있는 행동을 취한 뒤 visited에 기록을 하여 도착지점까지 이동하는 명령 횟수를 출력하면 된다.

현재 위치에서 로봇이 취할 수 있는 것은 크게 두가지다.

1) 1~3칸을 이동한다.

2) 오른쪽 또는 왼쪽으로 방향을 전환한다.

1번의 행동은 현재 바라보고 있는 방향으로 nx = x+dx[dir]*k 라는 점화식을 만들면 이동이 가능해진다.

2번의 행동은 각 방향에서 왼쪽 오른쪽을 nextDir = dDir[dir][k] 라는 점화식을 만들어서 이동이 가능 여부를 따진다.

이 때 각 위치 별로 4방향이 가능하므로 visited는 각 좌표 별로 [-1,-1,-1,-1] 을 선언하여 좌표와 방향의 중복을 체크하면 된다. 

-1을 선언하는 것으로 중복 체크와 함께 이동 횟수를 계산할 수 있다.

오답 노트

1~3칸이 이동이 가능한데 이때 나는 아래의 코드로 이동하였다.

for (let k = 1; k <= 3; k++) {
        const nx = cx + dx[cDir] * k;
        const ny = cy + dy[cDir] * k;
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visited[nx][ny][cDir] !== -1) continue;
        if (gr[nx][ny] === 1) continue
        visited[nx][ny][cDir] = visited[cx][cy][cDir] + 1;
        q.push([nx, ny, cDir]);
}

위 코드의 문제점은 로봇은 벽을 만나면 움직임을 멈춰야하는데 이 부분을 놓친 것이다.

k는 1부터 3으로 이동하는데 적게 이동했을 때 벽을 만났다면 이후에는 갈 필요가 없으니 

if(gr[nx][ny]===1) 일 경우 break를 주면 된다.

정답 코드

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

const dDir = [
    [3, 2],
    [2, 3],
    [0, 1],
    [1, 0],
];

const main = (input) => {
    const [n, m] = input[0].split(' ').map((v) => +v);
    const gr = [];
    for (let i = 1; i < n + 1; i++) {
        gr.push(input[i].split(' ').map((v) => +v));
    }
    const start = input[n + 1].split(' ').map((v) => +v - 1);
    const end = input[n + 2].split(' ').map((v) => +v - 1);

    const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => [-1, -1, -1, -1])
    );
    visited[start[0]][start[1]][start[2]] = 0;

    const q = [start];
    while (q.length) {
        const [cx, cy, cDir] = q.shift();

        if (cx === end[0] && cy === end[1] && cDir === end[2]) {
            console.log(visited[cx][cy][cDir]);
            process.exit(0);
        }
        for (let k = 1; k <= 3; k++) {
            const nx = cx + dx[cDir] * k;
            const ny = cy + dy[cDir] * k;
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny][cDir] !== -1) continue;
            if (gr[nx][ny] === 1) {
                break;
            }
            visited[nx][ny][cDir] = visited[cx][cy][cDir] + 1;
            q.push([nx, ny, cDir]);
        }
        for (let i = 0; i < 2; i++) {
            const nextDir = dDir[cDir][i];
            if (visited[cx][cy][nextDir] !== -1) continue;
            visited[cx][cy][nextDir] = visited[cx][cy][cDir] + 1;
            q.push([cx, cy, nextDir]);
        }
    }
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

main(input);