[JS][백준]14503_로봇 청소기

문제 번호

14503번: 로봇 청소기

 

 

알고리즘 분류

구현, 시뮬레이션

 

문제 풀이

 보통 시뮬레이션/구현 문제들은 문제에서 주어진 순서대로 작성하면 쉽게 문제가 해결되었다. 

그런데 이번 문제는 2단계의 b를 가장 마지막에 확인하였다. 문제에서 주어진 순서대로 작성하였더니 2단계의 b번을 확인하는 과정에서 아래의 c와 d를 확인하지않고 a와 b만 무한 반복하는 현상이 벌어졌기 때문이다. 물론 a b c d 순서대로 확인하는 방법도 있을거라 생각하지만 나는 a c d b 의 순서로 확인하였다.

 

문제풀이 진행중에 왼쪽으로 회전을 나타내기 위해서 사용할 배열이다. 북 동 남 서 방향을 보고있음을 뜻한다.

// 북 동 남 서
let diraction = [[-1, 0], [0, 1], [1, 0], [0, -1]];

 

문제에서 청소기는 한 번 청소한 구역은 다시 청소하지 않는다고 했기때문에 2차원 배열 visited를 생성하여서 해당 칸의 청소 여부를 확인한다. (이때 MAX는 52이다. 50으로 해도 상관없을것 같다. 처음에 문제에서 외벽이 주어지는지 모르고 52로 했다.)

let visited = new Array(MAX);
for (let i = 0; i < MAX; i++) {
  visited[i] = new Array(MAX).fill(false);
}

 

 

현재 있는 위치를 청소한적이 없다면 현재 위치를 청소한다.

 

  if (!visited[curY][curX]) {
    visited[curY][curX] = true;
    answer++;
    //console.log('stage1');
  }

 

다음은 2단계의 a를 진행한다. 왼쪽 방향에 청소하지 않은 공간이 있는지 확인하기 위해서 nextY 와 nextX 변수를 사용했다. 해당 변수들은 왼쪽 방향으로 회전한 후 한칸 전진했을때의 위치를 가리킨다.

curDiraction 과 nextDiraction은 diraction 배열의 인덱스를 가리키기 위해서 사용된다.

  let nextDiraction = curDiraction-1;
  if (curDiraction - 1 < 0)
      nextDiraction = 3;   
  let nextY = curY + diraction[nextDiraction][0];
  let nextX = curX + diraction[nextDiraction][1];

 

curY와 curX를 nextY 와 nextX 로 바꿨다는 것은 왼쪽 방향으로 회전한 후 한 칸 전진했다는 것을 의미한다.

  // 2단계.
  // step 1.  왼쪽 방향에 청소하지 않은 공간이 존재하면, 그 방향으로 회전하고 다음 한 칸을 전진하고 1번부터 진행한다.
  if (room[nextY][nextX] === 0 && !visited[nextY][nextX]) {        
    // 회전한다.
    curDiraction--;
    if(curDiraction < 0)
      curDiraction = 3;
    // 회전한 방향으로 한 칸을 전진한다.
    curY = nextY;
    curX = nextX;    
    //console.log('step1');
    continue;
  }

 

문제 순서대로라면 단계의 b를 검사해야할 차례지만 나는 c와 d를 먼저 검사했다. curDiraction은 현재 로봇 청소기가 바라보고 있는 방향을 나타낸다.(후진은 바라보고 있는 반대방향으로 움직여야 한다.) 그리고 curDiraciton은 diraction 배열의 인덱스를 가리키기 떄문에 0, 1, 2, 3 순서대로 북, 동, 남, 서 방향을 가리킨다.

// step 3.  네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  let check = 0;
  for (let next = 0; next < 4; next++) {    
    let nextY2 = curY + diraction[next][0];
    let nextX2 = curX + diraction[next][1];      
    if (room[nextY2][nextX2] === 1 || visited[nextY2][nextX2]){
      check++;      
    }        
  }  

  // step 4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
  if (check === 4) {
    // 북쪽
    if (curDiraction === 0) {
      if (room[curY + 1][curX] === 1){
        //console.log('north');
        break;
      }
      curY++;
      continue;
    }
    // 동
    if (curDiraction === 1) {
      if (room[curY][curX - 1] === 1){
        //console.log('east');
        break;
      }
      curX--;
      continue;
    }
    // 남
    if (curDiraction === 2) {
      if (room[curY - 1][curX] === 1){
        //console.log('south');
        break;
      }
      curY--;
      continue;
    }
    // 서
    if (curDiraction === 3) {
      if (room[curY][curX + 1] === 1){
        //console.log('west');
        break;
      }
      curX++;
      continue;
    }
  }

 

마지막으로 2단계의 b를 검사한다.

 // step 2.
   if (room[nextY][nextX] === 1 || visited[nextY][nextX]) {
    //console.log('step2');
    curDiraction--;
    if(curDiraction < 0)
      curDiraction = 3
    continue;

 

처음에는 a b c d 순서로 조건들을 검사하였다. 그러다보니 b단계에서

1. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

'2번으로 되돌아간다.' 를 continue 로 구현하려다보니 아래의 c와 d를 검사할 수 없었다.

c와 d는 check라는 변수가 4일 때만 동작하기때문에 순서를 바꾸어도 문제풀이에는 지장이 없었다.

 

 

전체코드

const { dir } = require('console');
const fs = require('fs');
const input = fs.readFileSync('로봇 청소기/input.txt').toString().split('\n');
const NM = input.shift().split(' ');
const N = Number(NM.shift());
const M = Number(NM.shift());
const init = input.shift().split(' ');
let curY = Number(init[0]);
let curX = Number(init[1]);
let curDiraction = Number(init[2]);
const MAX = 52;
let answer = 0;

// 북 동 남 서
let diraction = [[-1, 0], [0, 1], [1, 0], [0, -1]];

let room = new Array(MAX);
for (let i = 0; i < MAX; i++) {
  room[i] = new Array(MAX).fill(1);
}
for (let i = 0; i < N; i++) {
  let temp = input.shift().split(' ');  
  for (let j = 0; j < M; j++) {    
    room[i][j] = Number(temp[j]);    
  }
}

let visited = new Array(MAX);
for (let i = 0; i < MAX; i++) {
  visited[i] = new Array(MAX).fill(false);
}




let test = 1
while (1) {
  // 1단계.
  if (!visited[curY][curX]) {
    visited[curY][curX] = true;
    answer++;
    //console.log('stage1');
  }
  
  // 
  let nextDiraction = curDiraction-1;
  if (curDiraction - 1 < 0)
      nextDiraction = 3;   
  let nextY = curY + diraction[nextDiraction][0];
  let nextX = curX + diraction[nextDiraction][1];

  // 2단계.
  // step 1.  왼쪽 방향에 청소하지 않은 공간이 존재하면, 그 방향으로 회전하고 다음 한 칸을 전진하고 1번부터 진행한다.
  if (room[nextY][nextX] === 0 && !visited[nextY][nextX]) {        
    // 회전한다.
    curDiraction--;
    if(curDiraction < 0)
      curDiraction = 3;
    // 회전한 방향으로 한 칸을 전진한다.
    curY = nextY;
    curX = nextX;    
    //console.log('step1');
    continue;
  }  

  // step 3.  네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  let check = 0;
  for (let next = 0; next < 4; next++) {    
    let nextY2 = curY + diraction[next][0];
    let nextX2 = curX + diraction[next][1];      
    if (room[nextY2][nextX2] === 1 || visited[nextY2][nextX2]){
      check++;      
    }        
  }  

  // step 4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
  if (check === 4) {
    // 북쪽
    if (curDiraction === 0) {
      if (room[curY + 1][curX] === 1){
        //console.log('north');
        break;
      }
      curY++;
      continue;
    }
    // 동
    if (curDiraction === 1) {
      if (room[curY][curX - 1] === 1){
        //console.log('east');
        break;
      }
      curX--;
      continue;
    }
    // 남
    if (curDiraction === 2) {
      if (room[curY - 1][curX] === 1){
        //console.log('south');
        break;
      }
      curY--;
      continue;
    }
    // 서
    if (curDiraction === 3) {
      if (room[curY][curX + 1] === 1){
        //console.log('west');
        break;
      }
      curX++;
      continue;
    }
  }  

   // step 2.
   if (room[nextY][nextX] === 1 || visited[nextY][nextX]) {
    //console.log('step2');
    curDiraction--;
    if(curDiraction < 0)
      curDiraction = 3
    continue;
  }
}

console.log(answer);

 

특이사항

 '왼쪽으로 돈다' 와 '왼쪽으로 진행한다'의 차이점이 구현하는데 몇가지 헷깔리는 점들을 낳았다.

글로 읽었을땐 단순한 문제지만 코드로 나타내려고하니 두가지 표현때문에 막히는 시간이 상당히 늘어났었다.