[BOJ] 로봇청소기

[문제]

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

14503번: 로봇 청소기

[풀이]

 

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

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

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

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

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

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

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

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

 

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

 

 

#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; }