[백준] 14503번 로봇 청소기

14503번 로봇 청소기

---

1. 이해하기

• 맵의 끝부분은 모두 벽으로 되어 있다.
• 청소기는 바라보는 방향이 동, 서, 남, 북중 하나이다.
• 청소기는 다음과 같이 작동한다.
  1. 현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.
     • 왼쪽 방향에 아직 청소하지 않은 공간이 있다면, 그 방향으로 회전, 한칸을 전진하고 1번부터 진행한다.
     • 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
     • 네 방향 모두 청소가 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진하고 2번으로 돌아간다.
     • 네 방향 모두 청소가 되어있거나 벽이면서, 뒤쪽 방향이 벽이면 작동을 멈춘다.
• 로봇 청소기는 벽을 통과할 수 없다.
• 로봇 청소기가 청소한 영역의 크기를 출력.

---

2. 구현하기

• 청소기의 작동을 구현

  • 이때 입력이 청소기가 바라보는 방향이 0은 북, 1은 동, 2는 남, 3은 서쪽이기 때문에 왼쪽으로 회전하는 것은 방향 -1을 해준 것과 동일하다.
  • 왼쪽 방향에 청소할 공간이 없다면, 먼저 네 방향에 대해 탐색을 진행한다. 그리고 작동을 중지할지를 결정한다.
  • 청소기가 있는 현재 위치가 청소가 된 영역인지를 판단하고 아니면 청소를 진행, 청소한 영역의 크기를 하나 늘려준다.

  int move(int r, int c, int dir) {
      int ret = 0;
      int x = r, y = c;
      while(1) {
          if(!cleaned[x][y]) {
              ret++;
              cleaned[x][y] = true;
          }
          int n_dir = dir-1;
          if(n_dir < 0) n_dir = 3;
          int nx = x+dx[n_dir], ny = y+dy[n_dir];
          if(map[nx][ny] == 0 and !cleaned[nx][ny]) {
              x = nx; y = ny; dir = n_dir;
          } else {
              int cnt = 0;
              for(int i = 0; i < 4; i++) {
                  int nx = x+dx[i], ny = y+dy[i];
                  if(map[nx][ny] == 1 or cleaned[nx][ny]) cnt++;
              }
              if(cnt == 4) {
                  int n_dir = (dir+2)%4;
                  int nx = x+dx[n_dir], ny = y+dy[n_dir];
                  if(map[nx][ny] == 1) break;
                  else {
                      x = nx; y = ny;
                  }
              } else {
                  dir--;
                  if(dir < 0) dir = 3;
              }
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
int map[50][50];
bool cleaned[50][50];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int N,M;

int move(int r, int c, int dir) {
    int ret = 0;
    int x = r, y = c;
    while(1) {
        if(!cleaned[x][y]) {
            ret++;
            cleaned[x][y] = true;
        }
        int n_dir = dir-1;
        if(n_dir < 0) n_dir = 3;
        int nx = x+dx[n_dir], ny = y+dy[n_dir];
        if(map[nx][ny] == 0 and !cleaned[nx][ny]) {
            x = nx; y = ny; dir = n_dir;
        } else {
            int cnt = 0;
            for(int i = 0; i < 4; i++) {
                int nx = x+dx[i], ny = y+dy[i];
                if(map[nx][ny] == 1 or cleaned[nx][ny]) cnt++;
            }
            if(cnt == 4) {
                int n_dir = (dir+2)%4;
                int nx = x+dx[n_dir], ny = y+dy[n_dir];
                if(map[nx][ny] == 1) break;
                else {
                    x = nx; y = ny;
                }
            } else {
                dir--;
                if(dir < 0) dir = 3;
            }
        }
    }
    return ret;
}

int main() {
    cin >> N >> M;
    int r,c,dir;
    cin >> r >> c >> dir;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
    cout << move(r,c,dir) << '\n';

    return 0;
}