[백준 14503] 로봇 청소기

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

14503번: 로봇 청소기

#include <cstdio>
#include <cstring>
int R, C;
int board[50 + 2][50 + 2];
int clean;

int sx, sy, sd;


void input()
{
	scanf("%d %d", &R, &C);
	scanf("%d %d %d", &sx, &sy, &sd);
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			scanf("%d", &board[r][c]);
		}
	}
}


void simulation()
{
	// dir
	int dir_x[4] = { -1, 0, 1, 0 };
	int dir_y[4] = { 0, 1, 0, -1 };

	int nx = sx; 
	int ny = sy;
	int d = sd;
	int turn = 0;

	while (1) {
		// 1. 현재위치 청소
		if (board[nx][ny] == 0) {
			board[nx][ny] = 2;
			clean++;
			turn = 0;
		}

		// 2. 왼쪽방향부터 탐색 
		int nd = (d + 3) % 4;
		if (board[nx + dir_x[nd]][ny + dir_y[nd]] == 0) {
			d = nd;
			nx += dir_x[d];
			ny += dir_y[d];
			turn = 0;
			continue;
		}
		else {
			d = nd;
			turn++;
		}

		// 2-2, 2-3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우
		if (turn == 4) {
			if (board[nx - dir_x[d]][ny - dir_y[d]] != 1) {
				nx -= dir_x[d];
				ny -= dir_y[d];
				turn = 0;
			}
			else return;
		}
	}
}



int main()
{
	input();
	simulation();
	printf("%d\n", clean);
	return 0;
}

++ 22.12.10 갱신

1. 열끝, 행끝이 모두 1로 둘러쌓여져 있기 때문에 영역 밖으로 나가는 경우는 고려하지 않아도 된다. 

2. "네 방향 모두 탐색했는데 청소할 공간이 없는 경우"를 따지기 위해 turn 이라는 플래그를 두었다. turn이 4가 되면 네방향을 모두 탐색하고 처음 방향으로 되돌아 온 것이다.