알고리즘/코딩 테스트

[백준 14503] 로봇 청소기 - 구현, node.js,javascript

Judith Hopps 2023. 2. 14. 18:18
반응형

문제

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

 

14503번: 로봇 청소기

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽

www.acmicpc.net

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은  크기의 직사각형으로 나타낼 수 있으며, 1×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

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

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

 

알고리즘

0. 입력값을 저장한다.

//입력값 저장
const [r,c] = input[0].split(' ').map(Number)
let [y,x,d] = input[1].split(' ').map(Number)
let map = input.slice(2).map(v=>v.split(' ').map(Number))

1. 방향 객체를 생성한다.

-키는 방향으로 value는  [y,x]순이다.

// 북동남서 방향순
const dir = {0:[0,-1],1:[-1,0],2:[0,1],3:[1,0]}

2. while문으로 반복문 실행하고 주변에 0이 있을 시 처음으로 돌아간다.

이때, 4방향 모두 보기 위해 for문을 돌리는데 방향도는 순서가 반시계이므로 d-i이나 0이하로 될 가능성이 있으므로 +4를 해준뒤 4로 나눠준다.

d-i로 하지 않아서 20분동안 답이 잘못 나와 헤멨다...

 

또한 방향을 +3으로 바꿔줘야하므로 d-i+3+4로 해준다.

 

//청소 후 주변 탐색

while(true){
  
  if(map[y][x]===0){
    map[y][x]= 5;
    count++;
  }

  let i=0;
  for(;i<4;i++){
    let cur = (d-i+4)%4
    const [ny,nx] = [ y+dir[cur][0], x+dir[cur][1] ]
    
    if(map[ny][nx]===0){
        y= ny;x = nx;
        d= (d-i+7)%4
        break;
    }
  }
  
}

3. 주변에 0이 없을 시 후진한다.

//후진
  if(i===4){
    let back = (d+3) % 4
    const [ny,nx] = [ y+dir[back][0], x+dir[back][1] ]
    
    if(map[ny][nx]===1){
      break;
    }else{
      y=ny;x=nx;
    }
      
  }

 

4. 전체 코드

const fs = require('fs');
const path = require('path');
const filePath = process.platform === 'linux' ? '/dev/stdin' : path.join(__dirname, '/청소기.txt');
const input = fs.readFileSync(filePath).toString().trim().split('\n');

//입력값 저장
const [r,c] = input[0].split(' ').map(Number)
let [y,x,d] = input[1].split(' ').map(Number)
let map = input.slice(2).map(v=>v.split(' ').map(Number))

// console.log(map)

// 북동남서 방향순
const dir = {0:[0,-1],1:[-1,0],2:[0,1],3:[1,0]}

let count = 0;

//청소 후 주변 탐색
while(true){
  
  if(map[y][x]===0){
    map[y][x]= 5;
    count++;
  }

  let i=0;
  for(;i<4;i++){
    let cur = (d-i+4)%4
    const [ny,nx] = [ y+dir[cur][0], x+dir[cur][1] ]
    
    if(map[ny][nx]===0){
        y= ny;x = nx;
        d= (d-i+7)%4
        break;
    }
  }
  //후진
  if(i===4){
    let back = (d+3) % 4
    const [ny,nx] = [ y+dir[back][0], x+dir[back][1] ]
    
    if(map[ny][nx]===1){
      break;
    }else{
      y=ny;x=nx;
    }
      
  }
}


console.log(count)

 

 

이 문제는 골드 5이며 구현 문제이다. 

구현 문제는 연습만이 답이다...!! 계속 연습하자!!

반응형