[백준/G5] 14503 로봇 청소기

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

시간복잡도

O(N**2)

풀이

사실 구현자체는 문제에서 알려주는데로 하면 된다..하지만 풀면서 2가지 문제 & 고쳐야할 점이 있었는데

• 첫번째, 반시계방향으로 90도를 돈다는 게 한번 돌고 끝이 아니라 4방향을 다 돌면서 다음에 나갈 수 있는 곳을 찾는 것 (important 부분)
  • 당연하다...그게 바로 로봇청소기니까... 90도 돌아서 없다고 끝내면 안된다
• 두번째, bfs와 같은 알고리즘 기법은 필요 없는 문젠데 관성적으로 큐를 넣은 형식으로 풀었다는것이다...
  • 다시 돌아보니 그럴 필요가 애초에 없었다ㅎ 그냥 현재 위치만 업데이트하면 되는거라 q를 없애고 바꿨다.

최종코드

const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];

function cleaning(arr, N, M, x, y, rd) {
  let cnt = 0;

  while (true) {
    if (arr[x][y] === 0) {
      arr[x][y] = 2;
      cnt += 1;
    }

    // 현재 자리에서 주변 탐색
    let checkZero = false;
    for (let d = 0; d < 4; d++) {
      // (important) 찾을 때까지 계속 돌아가야 함
      rd = (rd + 3) % 4;
      let nx = x + dx[rd];
      let ny = y + dy[rd];

      if (nx < 0 && ny < 0 && nx >= N && ny >= M) continue;
			
      // 청소되지 않은 빈 칸이 있는 경우
      if (arr[nx][ny] === 0) {
        x = nx
				y = ny
        checkZero = true;
        break;
      }
    }

    // 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
    // (여기서 작동 멈춤이 일어날 수 있음)
    if (!checkZero) {
      let back = (rd + 2) % 4;
      let nx = x + dx[back];
      let ny = y + dy[back];

      if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
        if (arr[nx][ny] !== 1) {
          x = nx
					y = ny
        } else {
          return cnt;
        }
      } else {
        return cnt;
      }
    }
  }
}

// 로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./14503.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const [r, c, d] = input[1].split(" ").map(Number);
const arr = [];
let answer = 0;

for (let i = 2; i < N + 2; i++) {
  arr.push(input[i].split(" ").map(Number));
}

answer = cleaning(arr, N, M, r, c, d);

console.log(answer);

9376kb 108ms