로봇 청소기 (백준 14503)

문제

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

로봇 청소기가 있는 방은 N x M 크기의 직사각형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N−1,M−1)이다. 즉, 좌표 (r,c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

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

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

입력

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

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제 입력 1

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1

1

예제 입력 2

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2

57

---

🚀문제 접근

문제의 조건에 맞게 요구사항을 정리하면 다음과 같다.

1. 현재 위치를 청소한다. map[cy][cx] = 2
2. 반시계 방향으로 90도 회전하므로 왼쪽 방향부터 4방향 탐색을 진행한다.
   1. 만약 빈곳이 있다면 새로운 방향 및 좌표로 갱신한다. cy = ny, cx = nx
3. 빈 곳이 없다면 후진할 위치를 계산한다.
   1. 후진할 위치에 벽이 있다면 종료한다.
   2. 벽이 아니라면 해당 위치로 후진시킨다.

 

📌까다로웠던 부분

반시계 방향으로 로봇 청소기를 회전시키는 부분이 까다로웠다.

 

만약 dr이 0이라면 북쪽 방향을 바라보고 있기 때문에 반시계 방향으로 회전시킬 때 3 ➡ 2 ➡ 1 ➡ 0 순번이다.

또한 이 dr 값에 따라 y와 x축의 방향벡터가 결정되어야한다.

 

🛠코드

dfs인지 어떤 알고리즘으로 풀어야되는지 알고리즘만 찾다가 못풀었다...

이런 빡구현 문제도 많이 연습해야겠다.

let input = require('fs').readFileSync(0).toString().trim().split('\n');
let [n, m] = input[0].split(' ').map(Number);
let [r, c, d] = input[1].split(' ').map(Number);
let map = input.slice(2).map((elem) => elem.split(' ').map(Number));

// dr: 북 동 남 서
const dy = [-1, 0, 1, 0];
const dx = [0, 1, 0, -1];

function solution(cy, cx, dr) {
  let ret = 0; // 청소한 공간 수
  while (true) {
    // 1. 현재위치 청소
    map[cy][cx] = 2;
    ret += 1;
    // 2. 왼쪽방향으로 순서대로 탐색해서 청소하지 않은 영역이 있으면 이동
    let flag = 1;
    while (flag) {
      // 왼쪽부터 네방향중 미청소 영역 있는 경우
      for (const nd of [(dr + 3) % 4, (dr + 2) % 4, (dr + 1) % 4, dr]) {
        const ny = cy + dy[nd];
        const nx = cx + dx[nd];
        // 청소가 안된 영역이라면 새로운 방향 및 좌표 갱신
        if (map[ny][nx] === 0) {
          cy = ny;
          cx = nx;
          dr = nd;
          flag = 0;
          break;
        }
      }
      if (!flag) break;
      // 4방향 모두 미청소 영역이 없다 ➡ 후진을 해야함
      // 후진할 위치 계산
      let by = cy - dy[dr];
      let bx = cx - dx[dr];
      // 후진위치가 벽이면 종료
      if (map[by][bx] === 1) return ret;
      else {
        cy = by;
        cx = bx;
      }
    }
  }
}

console.log(solution(r, c, d));