백준 14503 - 로봇 청소기

문제링크

• 백준 14503

문제설명

• N x M 크기의 방이 1 x 1 크기의 정사각형으로 나누어져 있다.
• 각 칸은 청소되지 않은 칸(0) 혹은 벽(1) 으로 구성된다.
• 로봇 청소기는 동,서,남,북 중 하나의 방향을 바라보고 있고, 다음과 같은 로직에 따라 움직인다.
  1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
  2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
  • 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 후진하고 1번으로 돌아간다.
  • 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
    1. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
  • 반시계 방향으로 90도 회전한다.
  • 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
  • 1번으로 돌아간다.
• 로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 구하라

문제접근

• 순서에 주의하여 구현하면 된다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

int N, M, xpos, ypos, dir, ans = 0;
int board[50][50]; // 0: no clean, 1: wall, 2: clean completed
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void doClean() {
	if (board[xpos][ypos] == 0) {
		board[xpos][ypos] = 2;
		ans++;
	}
}

bool checkNoCleanNearArea() {
	int noClean = 0;
	for (int d = 0; d < 4; d++) {
		int nx = xpos + dx[d];
		int ny = ypos + dy[d];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (board[nx][ny] == 0) noClean++;
	}
	if (noClean == 0) return false;
	else return true;
}

bool backMove() {
	// back direction
	int bdir = (dir+2) % 4;
	int nx = xpos + dx[bdir];
	int ny = ypos + dy[bdir];
	if (nx < 0 || nx >= N || ny < 0 || ny >= M) return false;
	if (board[nx][ny] == 1) return false;
	xpos = nx;
	ypos = ny;
	return true;
}

void forwardMove() {
	int nx, ny;
	dir = (dir + 3) % 4;
	nx = xpos + dx[dir];
	ny = ypos + dy[dir];
	if (nx < 0 || nx >= N || ny < 0 || ny >= M) return;
	if (board[nx][ny] == 0) {
		xpos = nx;
		ypos = ny;
	}
}

void robot_proc() {
	while (true) {
		doClean();
		if (checkNoCleanNearArea()==false) {
			if (backMove() == false) break;
		}
		else {
			forwardMove();
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	scanf("%d %d", &N, &M);
	scanf("%d %d %d", &xpos, &ypos, &dir);

	int val = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &board[r][c]);
		}
	}
	robot_proc();
	printf("%d\n", ans);
	return 0;
}