<Baekjoon> #14503 Simulation_로봇청소기 c++

#14503 로봇청소기
참고

✍문제 정리

• 로봇 청소기가 바라보는 방향은 북(0), 동(1), 남(2), 서(3) 중 하나이다
• 현재 위치를 청소하고 현재 위치에서 현재 방향을 기준으로 왼쪽 부터 탐색한다
• 왼쪽에 청소하지 않은 공간이 있으면 그 방향으로 회전하고 이동하고 위부터 반복한다
• 왼쪽 방향에 청소할 공간이 없다면 왼쪽 방향을 현재 방향으로 만들어주고 그 방향을 기준으로 왼쪽을 탐색한다
• 처음 방향을 기준으로 왼쪽으로 회전하고 왼쪽 방향을 탐색하는 것을 4번 반복했을 때 이미 청소가 되어 있거나 벽이어서 청소할 곳이 없다면 현재 바라보는 방향을 기준으로 한 칸 후진하고 다시 현재 방향을 기준으로 왼쪽 방향부터 탐색한다
• 네 방향 모두 청소가 되어 있거나 벽이면서 뒤쪽 방향이 벽이라 후진도 할 수 없을 때 작동을 멈춘다

👩‍💻1. Initialize

• 문제에서 주어진 순서대로 북,동,남,서 방향을 만들어준다

int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

• map상에서 빈 공간, 벽이 있는 공간, 이미 청소한 공간을 표시한다

enum {EMPTY, WALL, CLEANED};

👩‍💻2. Turn Direction

• 현재 바라보고 있는 방향을 기준으로 왼쪽으로 돌렸을 때, 현재 바라보고 있는 방향이 북,동,남,서 중 어느 곳인지를 return 한다
  
  이렇게 현재 바라보고 있는 방향에 따라 왼쪽으로 회전했을 때 현재 가리키는 방향이 바뀐다

int turnDir(int dir) {
	switch (dir) {
	case 0: return 3;
	case 1: return 0;
	case 2: return 1;
	case 3: return 2;
	}
}

👩‍💻3. move()

• 한 번 회전했을 때 청소할 수 있는 곳인지 bool cleaned를 두어 관리하고, 네 방향으로 모두 돌았을 때 모두 청소할 수 없는 곳인지 확인하기 위해 cannotCleaned라는 변수를 두어, 이 값이 4가 되면 현재 방향을 기준으로 뒤로 이동하는 연산을 수행하게 한다
• 현재 위치는 (y,x), 현재 방향은 d이다. 여기서 d방향을 기준으로 왼쪽으로 이동했을 때 방향은 nd이다.
• 현재 위치를 기준으로 왼쪽으로 회전하여 한 칸 이동했을 때 좌표 (ny,nx)가 빈공간이면 네 방향 탐색을 중단하고 해당 위치를 청소한 후 현재 좌표와 방향 (y,x), d을 (ny, nx), nd로 변경해준다

if (map[ny][nx] == EMPTY) {
	cleaned = true;
	break;
}
......
if (cleaned) {
	map[ny][nx] = CLEANED;
	cnt++;
	d = nd;
}
......
y = ny; x = nx;

• 현재 위치를 기준으로 왼쪽 방향을 탐색했을 때 벽,이미 청소한 구역, map의 범위를 벗어난 구역일 경우 현재 방향d을 왼쪽으로 돌린 방향nd으로 바꾸어주고 한 번 바꿀 때마다 cannotCleaned++를 해준다

else if (map[ny][nx] != EMPTY ||
    ny < 0 || nx < 0 || ny >= N || nx >= M) {
	d = nd;
	cannotCleaned++;
}

• cannotClean==4 이면, 즉 4 방향을 모두 돌아 원래 방향으로 돌아왔을 때, 뒤로 한 칸 후진하고 다시 탐색을 한다. 만약 한 칸 후진한 값이 벽이거나 map의 범위를 벗어날 때 중단한다

if (cannotCleaned == 4) {
	ny = y - dy[d];
	nx = x - dx[d];
	if (ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx] == WALL) break;
}
y = ny;
x = nx;

전체코드

#include <iostream>
#include <vector>
using namespace std;

enum {EMPTY, WALL, CLEANED};

int N, M,r,c,d;
vector<vector<int>> map;

int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

int turnDir(int dir) {
	switch (dir) {
	case 0: return 3;
	case 1: return 0;
	case 2: return 1;
	case 3: return 2;
	}
}
void move(int y, int x, int dir) {
	int cnt = 0;
	map[y][x] = CLEANED;
	cnt++;

	while (1) {
		int ny, nx, nd;
		bool cleaned = false;
		int cannotCleaned = 0;

		for (int i = 0; i < 4; i++) {
			nd = turnDir(d);
			ny = y + dy[nd];
			nx = x + dx[nd];

			if (map[ny][nx] == EMPTY) {
				cleaned = true;
				break;
			}
			else if (map[ny][nx] != EMPTY || ny < 0 || nx < 0 || ny >= N || nx >= M) {
				d = nd;
				cannotCleaned++;
			}
		}
		if (cleaned) {
			map[ny][nx] = CLEANED;
			cnt++;
			d = nd;
		}
		if (cannotCleaned == 4) {
			ny = y - dy[d];
			nx = x - dx[d];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx] == WALL) break;
		}
		y = ny;
		x = nx;
	}
	cout << cnt << endl;
}
void init() {
	cin >> N >> M;
	cin >> r >> c >> d;
	map = vector<vector<int>>(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
}

int main() {
	init();
	move(r, c, d);

	return 0;
}