[BOJ] 로봇청소기

[문제]

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

14503번: 로봇 청소기

[풀이]

 

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

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

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.

   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

2) 조건에 맞춰서 bfs를 작성하고 완탐을 한다. 단, 로봇청소기는 한 방향을 기준으로 왼쪽으로 움직이기 때문에 큐에 넣을 조건이 된다면 (왼쪽 방향에 청소할 공간이 있다면) 더 이상 다른 방향을 탐색하지 않고 바로 그 방향으로 가도록 break를 걸어줘야 한다. 

 

3) flag 변수를 두어 상 하 좌 우 모두 청소할 공간이 없다면 (false) 후진을 할 수 있도록 한다. 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

#include <iostream> #include <vector> #include <queue> using namespace std;   int n, m; int map[51][51]; typedef pair<int, int> pp; typedef pair<int, pp> ipp; bool visited[51][51]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   void bfs(int sx, int sy, int dir) {     queue<ipp> q;     q.push(ipp(dir, pp(sx, sy)));       int res = 1;     visited[sx][sy] = true;     while (!q.empty())     {         int x = q.front().second.first;         int y = q.front().second.second;         int d = q.front().first;         int n_d = d;         q.pop();           //현재 방향부터 왼쪽 방향을 살펴본다.                   bool flag =false; //청소할 공간이 있는지 없는지 확인한다.         for (int i = 0; i < 4; i++)         {             n_d = n_d -1 < 0 ? 3 : n_d-1;             int nx = x + dx[n_d];             int ny = y + dy[n_d];               if (nx <= 0 || nx >= n-1 || ny <= 0 || ny >= m-1 || map[nx][ny] || visited[nx][ny]) continue;               q.push(ipp(n_d, pp(nx, ny)));             res++;             visited[nx][ny] = true;             flag = true;             break;         }         if (!flag)         {             //네 방향 모두 봤는데 청소할 곳이 없을 때             int b_d = d < 2 ? d+2 : d-2;             int nx = x + dx[b_d];             int ny = y + dy[b_d];               if (nx <= 0 || nx >= n-1 || ny <= 0 || ny >= m-1) continue;             if (!map[nx][ny]) {                 q.push(ipp(d, pp(nx, ny)));             }         }     }     cout << res << '\n'; } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);     int x, y, d;     cin >> n >> m >> x >> y >> d;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             cin >> map[i][j];         }     }       bfs(x, y, d);     return 0; }