[백준] 14503번 로봇 청소기

14503번: 로봇 청소기

단순한 DFS 문제인 줄 알고 대충 읽고 짜다가 갈아엎었다.

시뮬레이션 문제이므로 작동 순서를 잘 읽고 구현해야 한다.

 

1. 현재 방향에서 왼쪽 방향으로 일단 회전하고 그 방향의 공간이 비어있는지 확인한다.

 

2. 청소하지 않은 빈 공간이라면 -> 전진한다. (재귀)

벽이거나 청소를 한 공간이라면 -> 왼쪽 방향으로 한 번 더 회전한다.

 

3. 왼쪽 방향으로 총 네 번 회전하며 확인했는데도 빈 공간이 없을 경우

현재 방향은 그대로 뒤로 후진한다.

 

4. 후진할 공간이 벽이면 작동을 멈추고

벽이 아니라면 후진한다.

 

이때 재귀에서 돌아오는 경우는

작동이 멈춘 경우일 뿐이므로

재귀에서 돌아오면 return을 해주어 전부 멈추게 하는 게 포인트다.

#include <iostream>
using namespace std;
int N, M, r, c, d, x, y, res = 1;
int arr[51][51], dd[4] = { 3, 0, 1, 2 }, dx[4] = { 0, -1, 0, 1 }, dy[4] = { -1, 0, 1, 0 }, back_dx[4] = { 1, 0, -1, 0 }, back_dy[4] = { 0, -1, 0, 1 };
void Dfs(int d, int r, int c) {
	int cnt = 0, clear = 0;
	while (clear != 4) {
		x = r + dx[d], y = c + dy[d]; //현재 방향의 왼쪽 방향의 공간
		d = dd[d]; //왼쪽 방향으로 회전
		if (arr[x][y] == 0) { //그 공간이 청소하지 않은 공간일 때
			arr[x][y] = -1, res++; //청소 후
			Dfs(d, x, y); //한 칸 전진
			return;
		}
		else clear++;
	}
	//더 이상 청소할 곳이 없으면 후진할 차례
	x = r + back_dx[d], y = c + back_dy[d];
	if (arr[x][y] == 1) return; //후진할 곳이 벽이면 작동 종료
	else Dfs(d, x, y); //아니면 그냥 후진
}

int main() {
	cin >> N >> M >> r >> c >> d;
	for (int n = 0; n < N; n++) for (int m = 0; m < M; m++) cin >> arr[n][m];
	arr[r][c] = -1;
	Dfs(d, r, c);
	cout << res;
	return 0;
}