[BOJ][C++] 14503 로봇청소기

[BOJ][C++] 14503 로봇청소기

풀이

1. 청소를 한다.

이 때 한 번 청소한 곳은 또 방문하면 안되기 때문에 visited를 이용합니다. 방향을 바꿀땐 사방을 다 탐색하면 후진해야하기 때문에 이를 cnt를 이용해 꼭 체크해줍니다.

1-1. map[nx][ny]가 청소할 수 있을 때 (map[nx][ny]==0 && visited[nx][ny]==0) : 다음 좌표, dir 바꾸어 func호출

1-2. map[nx][ny]가 청소할 수 없을 때  : 청소기의 방향 회전이 필요합니다. = dir, cnt+1 로 func호출

2. 후진해야 하는 경우 (cnt==4)

cnt==4 일때는 사방이 벽이거나 청소를 한 경우입니다. 이 때, 후진을 해줘야하는데 후진을 할 수 있다면 다음 좌표로 옮기면 되고, 후진이 불가능하면 종료해주면 됩니다.

2-1. 후진이 가능한 경우 : 범위체크와 벽이 아닌 경우 = 다음 좌표, dir 그대로

2-2. 후진이 불가능한 경우 : 종료(return)

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string.h>
using namespace std;
int n, m;
int r, c, d;
int res = 1;
int map[51][51];
int visited[51][51];
int dx[] = { 0,-1,0,1 }; // 회전 좌표
int dy[] = { -1,0,1,0 };
int bx[] = {1,0,-1,0}; // 후진 좌표
int by[] = {0,-1,0,1};
void cleaning(int x, int y, int dir, int cnt) {
	if (cnt == 4) {
		//후진
		int nx = x + bx[dir];
		int ny = y + by[dir];
		if (map[nx][ny] == 1 || nx <= 0 || ny <= 0 || nx >= n - 1 || ny >= m - 1) {
			return;
		}
		else {
			cleaning(nx, ny, dir, 0);
		}
	}
	else {
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		//청소가능
		if (map[nx][ny] == 0 && visited[nx][ny]==0) {
			res++;
			visited[nx][ny] = 1;
			if (dir - 1 < 0) dir = 4;
			cleaning(nx, ny, dir - 1, 0);
		}
		//불가능
		else {
			if (dir - 1 < 0) dir = 4;
			cleaning(x, y, dir - 1, cnt + 1);
		}
	}
}
int main() {
	scanf("%d %d", &n, &m);
	scanf("%d %d %d", &r, &c, &d); //현재위치rc, 방향d
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	visited[r][c] = 1;
	cleaning(r, c, d, 0);
	printf("%d", res);
}