문제
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다. baekjoon
코드
#include <iostream>
#include <vector>
using namespace std;
// 북 동 남 서
int dir_x[] = {-1, 0, 1, 0}, dir_y[] = {0, 1, 0, -1};
int back_x[] = {1, 0, -1, 0}, back_y[] = {0, -1, 0, 1};
int main() {
int n, m;
cin >> n >> m;
int r, c, d;
cin >> r >> c >> d;
vector<vector<int>> v(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) cin >> v[i][j];
}
vector<vector<bool>> cleaned(n, vector<bool>(m, false));
int result = 0;
while (true) {
// 1. 현재 방향 청소
if (v[r][c] == 0 && !cleaned[r][c]) {
cleaned[r][c] = true;
result++;
}
// 2-a, 2-b
bool to_1 = false;
int wave = 0;
while (wave < 4) {
d--;
if (d == -1) d = 3;
int nr = r + dir_x[d], nc = c + dir_y[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
if (v[nr][nc] == 0 && !cleaned[nr][nc]) {
r = nr; c = nc;
to_1 = true;
break;
}
wave++;
}
// 2-c, 2-d
if (!to_1) {
int br = r + back_x[d], bc = c + back_y[d];
if (v[br][bc] == 1 || br < 0 || bc < 0 || br >= n || bc >= m) break;
r = br; c = bc;
}
}
cout << result << '\n';
}
풀이
청소 여부를 판단하는 벡터를 하나 더 둬서 관리했다. 시뮬레이션 문제라 문제가 시키는 대로 하면 된다. 디버깅 할 때 문제에서 주어진 1번부터 2.d번까지 코드랑 같이 따라가다 보면 처리 못 한 부분이 보인다.