[백준] 14503 로봇 청소기 - javascript

📌 문제

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

📌 풀이

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

const [n, m] = input.shift().split(" ").map(Number);
let [x, y, d] = input.shift().split(" ").map(Number);
const arr = input.map(i => i.split(" ").map(Number));
const visited = Array.from({ length: n }, () =>
  Array.from({ length: m }, () => false)
);
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];

let ans = 0;
let cnt = 0;

while (1) {
  if (cnt === 4) {
    const [backx, backy] = [x + dx[(d + 6) % 4], y + dy[(d + 6) % 4]];
    if (arr[backx][backy] === 1) break;
    else {
      x = backx;
      y = backy;
      cnt = 0;
    }
  }
  
  if (!visited[x][y]) {
    visited[x][y] = true;
    arr[x][y] = 2;
    ans++;
  }

  const [leftx, lefty] = [x + dx[(d + 3) % 4], y + dy[(d + 3) % 4]];
  if (arr[leftx][lefty] === 0) {
    x = leftx;
    y = lefty;
    cnt = 0;
  } else {
    cnt++;
  }
  d = (d + 3) % 4;
}

console.log(ans);

✔ 알고리즘 : 구현

✔ 방문 체크를 위한 배열 visited, 방향 체크를 위한 dx, dy를 가지고 해결했다.

✔ 1. 현재 현재 위치를 청소한다.

if (!visited[x][y]) {
  visited[x][y] = true;
  arr[x][y] = 2;
  ans++;
}

청소한 좌표와 벽의 좌표를 구별하기 위해 청소한 좌표는 2로 설정하였다.

✔ 2-a. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다.

const [leftx, lefty] = [x + dx[(d + 3) % 4], y + dy[(d + 3) % 4]];
if (arr[leftx][lefty] === 0) {
  x = leftx;
  y = lefty;
  cnt = 0;
} else {
  cnt++;
}
d = (d + 3) % 4;

if문이 빈 공간이 존재 하는 경우 else문이 그렇지 않을 경우이다. 두 경우 모두 왼쪽 방향으로 회전하는 것은 동일하다.

✔ 2-b. 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면 한 칸 후진한다.

위에서 else문에서만 cnt를 증가시켜서 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우 를 체크하였다.

if (cnt === 4) {
  const [backx, backy] = [x + dx[(d + 6) % 4], y + dy[(d + 6) % 4]];
  if (arr[backx][backy] === 1) break;
  else {
    x = backx;
    y = backy;
    cnt = 0;
  }
}

✔ 난이도 : 백준 기준 골드 5

✔

✔