반응형
▷ 문제 : 14503번 - 로봇 청소기
▷ 해결 날짜 : 2022.07.27
▷ 소요 시간 : 1시간 30분
▷ 풀이 과정 :
문제는 아래에서 제시하는 조건만 숙지하여 풀면 되는 문제이다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.
- 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
- 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
* 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
* 방향은 동, 서, 남, 북 4방향으로 이루어져 있다.
문제 자체는 생각보다 어렵지 않다.
조건들만 잘 처리해주면 되는것인데, 풀다가 꼬여서 다시 처음부터 푸느라 시간이 좀 걸렸다.
진짜 그냥 저 조건 순서대로 풀었다.
▷ 구현
let fs = require("fs");
let input = fs.readFileSync("./dev/stdin").toString().split("\n");
// 상, 우, 하, 좌
const ds = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1],
];
const [N, M] = input.shift().split(" ").map(Number);
const [startX, startY, direction] = input.shift().split(" ").map(Number);
const graph = input.map((v) => v.split(" ").map(Number));
const visited = Array.from(Array(N), () => Array(M).fill(0));
const maxDs = ds.length;
const getPositivePosition = (num) => (num < 0 ? num + maxDs : num);
let count = 0;
const queue = [[startX, startY, direction]];
while (queue.length) {
let [x, y, dir] = queue.shift();
// 1. 현재 위치 청소
if (!graph[x][y] && !visited[x][y]) {
count++;
visited[x][y] = 1;
}
// 동, 서, 남, 북 체크
for (let i = 0; i < 4; i++) {
// 2. 왼쪽방향 회전
dir = getPositivePosition(--dir);
const nx = x + ds[dir][0];
const ny = y + ds[dir][1];
// 2-1 왼쪽방향에 청소가 가능하면 이동
if (!graph[nx][ny] && !visited[nx][ny]) {
queue.push([nx, ny, dir]);
break;
}
// 2-3, 2-4 네 방향 모두 청소가 이미 되어있거나 벽인 경우 진입
if (i === 3) {
const backDir = getPositivePosition(dir - 2);
const bx = x + ds[backDir][0];
const by = y + ds[backDir][1];
// 후진이 가능한 경우 후진 (이미 청소했던 부분이여도 상관없음 벽만 아니면)
if (!graph[bx][by]) {
queue.push([bx, by, dir]);
break;
}
}
// 2-2 왼쪽 방향에 청소할 공간이 없다면 회전만 하고 다시 컨티뉴
}
}
console.log(count);
▷ 복기 :
역시 그냥 풀다가 꼬인거 같으면 다시 처음부터 푸는 게 더 빠르다.
반응형
댓글