[백준 14503] 로봇 청소기 - 구현, node.js,javascript
문제
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번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 90∘ 회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 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이며 구현 문제이다.
구현 문제는 연습만이 답이다...!! 계속 연습하자!!