[baekjoon 14503] 로봇 청소기 (구현, 시뮬레이션) (C++)

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

14503번: 로봇 청소기

로봇 청소기가 청소할 수 있는 영역의 개수를 구해야 한다.

일반 4방향 탐색이 아닌, 기본적으론 반시계 방향 탐색을 하며 여러 가지 규칙이 있다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 

사실 구현, 시뮬레이션 문제는 규칙 따라 하라는 대로 하면 풀린다. 하지만 보통 규칙이 복잡해서 정리가 안된다.

나의 경우 규칙 2-3을 제대로 읽지 않아서 디버깅에 시간을 좀 썼다.

"네 방향 모두 청소가 이미 되어있거나 벽인 경우에는" 이란 키워드에 집중해서 후진도 저 케이스에는 못하는 걸로 생각했다. 하지만 후진은 벽이 아니면 가능하다!

또한, 2-1이 부합하면 회전 후 한 칸 전진이고, 2-2면 그냥 회전만 한다.

 

나머지 조건은 귀찮은 조건들이어서 차근차근 풀었다.

1번 조건은 그 영역을 청소한다 이므로 그냥 flag를 이용해서 cnt++만 해주었다.

그리고 2번 조건은 왼쪽 방향부터 차례차례 4방향을 봐야 하므로 for문을 이용해주었고

2-1 조건에 부합하면 for문을 벗어나 주었다.

2-2 조건에 부합하면 for문을 벗어나지 않고 다음 방향으로 회전만 하고 계속 진행.

2-3 조건에 부합하면 방향 따라 후진하고 후진 가능하면 후진, 아니면 종료했다.

 

#include <iostream>

using namespace std;

int n, m, room[51][51], r, c, d, check[51][51];
int moving[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int searching(int startX, int startY, int dir) {
	int cnt = 0;
	int x = startX, y = startY, d = dir;
	int searchFlag = true;
	while (1) {
		if (searchFlag) { // 청소 가능하면 그 영역을 청소하고 영역을 센다.
			if (!check[x][y]) {
				cnt++;
				check[x][y] = true;
			}
		} // 아니면 바로 조건 2번(반시계 4방향 탐색 시작)
		searchFlag = false; // 조건 2-b, 2-c를 위해서 매번 초기화
		for (int i = 0; i < 4; i++) {
			int nd = (d + 3) % 4;
			int nx = x + moving[(d + 3) % 4][0];
			int ny = y + moving[(d + 3) % 4][1];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (room[nx][ny] == 0 && !check[nx][ny]) {
					x = nx;
					y = ny;
					d = nd;
					searchFlag = true;
					break;
				} // 다시 1번으로(현재 위치 청소)
				else if (room[nx][ny] == 1 || check[nx][ny]) {
					check[nx][ny] = true;
					d = nd; // 방향만 갱신해준다.
					continue; // 다른 방향을 봐야하므로 for문을 벗어나지 않는다.
				}
			}
		}
		if (!searchFlag) { // 4방향 이미 청소되어 있다면 방향 그대로 후진
			x = x + moving[(d + 2) % 4][0];
			y = y + moving[(d + 2) % 4][1];
			if (x < 0 || y < 0 || x >= n || y >= m)
				return cnt;
			if (room[x][y] == 0) // 벽이 아니면 계속 진행
				continue;
			if (check[x][y]) // 벽 + 후진했는데 이미 청소한 곳이면 종료
				return cnt;
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	cin >> r >> c >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> room[i][j];
		}
	}
	cout << searching(r, c, d);
}