[JS] 백준 14503번 : 로봇청소기

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

14503번: 로봇 청소기

 

 

 

📋풀이방법

1. 현재 칸이 청소되지않은 경우 청소한다.

   2-1. 90도 회전하고, 그 앞의 구역이 청소되지않은 구역이면 전진한다. - 체크는 0번으로 초기화해준다

   2-2. 90도 회전하고, 그 앞의 구역이 청소가능한 구역이 아니면 체크 후 90도 회전한다

3. 체크가 4번이 되었다면 바라보고 있는 방향에서 뒤쪽의 구역을 확인한다

  4-1. 만약 뒤쪽의 구역이 벽이면 멈춘다.

  4-2.만약 뒤쪽의 구역이 벽이 아니면 후진한다. -체크는 0번으로 초기화한다.

 

🤟내 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [n,m] = input.shift().split(" ").map(Number);
let [r,c,d] = input.shift().split(" ").map(Number);
let arr=[];
for(var i=0;i<n;i++){
    arr.push(input[i].split(" ").map(Number));
}

let dx= [0,1,0,-1];
let dy =[-1,0,1,0];
let answer=0;
let cnt=0;
//반시계방향 90도씩 한번씩 회전하면서 청소가능구역인지 확인 후 반복
while(1){
    //4칸중 청소되지않은 빈칸이 없는 경우
    if(cnt==4){
        const [By, Bx] = [r + dy[(d + 6) % 4], c+ dx[(d + 6) % 4]];
        if(arr[By][Bx]==1) break;
        else{
            r=By
            c=Bx;
            cnt=0;
        }
    }
    //현재 위치 청소
    if(arr[r][c]==0) {
        answer++;
        arr[r][c]=2;
    }
    //반시계방향 90도 회전해서 앞쪽 방향 청소가능구역인지 확인
    const [Ly, Lx] = [r + dy[(d + 3) % 4], c + dx[(d + 3) % 4]];
    //앞의 방향이 청소가능구역이면
    if (arr[Ly][Lx] === 0) {
        r = Ly;
        c = Lx;
        cnt = 0;
    }
    //앞의방향이 청소 가능하지 않는 구역이면
    else {
        cnt++;
    }
    //반시계방향 90도 회전 후 반복 재시작
    d = (d + 3) % 4;
    
}
console.log(answer)

 

💢어려웠던 이유

1. 처음에 DFS로 구현하려했지만 문제를 제대로 이해하지않고 풀이를 시작해 꼬여버렸다.

로봇 청소기는 다음과 같이 작동한다.

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

위 부분을 아래의 풀이 방법으로 잘 변경시켜야한다.

1. 현재 칸이 청소되지않은 경우 청소한다.

   2-1. 90도 회전한 앞의 방향이 청소되지않은 구역이면 전진한다. - 체크는 0번으로 초기화해준다

   2-2. 90도 회전한 앞의 방향이 청소가능한 구역이 아니면 체크한다.

3. 90도회전한다 - 회전한 앞의 방향이 가능구역이든 가능구역이 아니든 무조건 90도회전 해야하므로 -즉 90도 회전한 앞의 방향을 먼저 체크하고 회전한다.

4. 체크가 4번이 되었다면 바라보고 있는 방향에서 뒤쪽의 구역을 확인한다

  5-1. 만약 뒤쪽의 구역이 벽이면 멈춘다.

  5-2.만약 뒤쪽의 구역이 벽이 아니면 후진한다. -체크는 0번으로 초기화한다.

 

즉 풀이 방식은 한번 90도 회전하는 것을 기준으로 반복해야한다.

 

2. 90도 회전했을 때의 북 동 남 서 - 0 1 2 3 을 어떻게 변화시켜야 할 지 파악하지 못했다.

-만약 0에서 반시계 방향으로 90도 회전하면 3이 되어야한다.

-이 공식은 아래와 같다

[r + dy[(d + 3) % 4], c + dx[(d + 3) % 4]];

 즉 현재 좌표 + (바라보고 있는 방향+3) % 4 이 된다.

나온 값으로 x좌표와 y좌표에 알맞은 좌표 증가 또는 좌표감소 값(상하좌우를 표현하는 dx,dy배열)을 더해주면된다.