[#14503] 로봇 청소기

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int n, m;  //판 크기
int row, col, dir;  //로봇 청소기의 위치, 방향
vector<vector<int>> board;  //벽 여부
vector<vector<bool>> isClean;  //청소 여부

int dRow[4] = { -1,0,1,0 };  //북동남서
int dCOl[4] = { 0,1,0,-1 };

//범위 검사
bool inRange(int r, int c) {
	if (0 <= r && r < n && 0 <= c && c < m)
		return true;

	return false;
}

//왼쪽으로 돌리기
void rotate() {
	dir--;
	if (dir == -1)
		dir = 3;
}

//한칸 전진.
void moveForward() {
	//dir 0 1 2 3 북 동 남 서
	row = row + dRow[dir];
	col = col + dCOl[dir];
}

//한칸 후진
void moveBack() {
	//dir 0 1 2 3 북 동 남 서

	int backDir;  //후진할 방향
	if (dir == 0 || dir == 1)
		backDir = dir + 2;
	else if (dir == 2 || dir == 3)
		backDir = dir - 2;

	row = row + dRow[backDir];
	col = col + dCOl[backDir];
}

//뒤에 공간이 있는지
bool hasBackSpace() {
	int backDir;
	if (dir == 0 || dir == 1)
		backDir = dir + 2;
	else if (dir == 2 || dir == 3)
		backDir = dir - 2l;

	//뒷 부분 좌표
	int nextRow = row + dRow[backDir];
	int nextCol = col + dCOl[backDir];

	//범위를 넘거나 범위 안에 있지만 벽이면 false return
	if (!inRange(nextRow, nextCol) || board[nextRow][nextCol] == 1)
		return false;

	return true;
}

//왼쪽에 청소할 수 있는 공간이 있는지
bool hasLeftSpace() {
	int nextRow = row;
	int nextCol = col;
	if (dir == 0) {
		//북
		nextCol += -1;
	}
	else if (dir == 1) {
		//동
		nextRow += -1;
	}
	else if (dir == 2) {
		//남
		nextCol += 1;
	}
	else if (dir == 3) {
		//서
		nextRow += 1;
	}

	//범위안에 있으면서 벽도 아니고 청소도 안되어있으면 true
	if (inRange(nextRow, nextCol) && board[nextRow][nextCol] == 0 && !isClean[nextRow][nextCol])
		return true;

	return false;
}

int main() {
	scanf("%d %d", &n, &m);
	scanf("%d %d %d", &row, &col, &dir);

	board = vector<vector<int>>(n, vector<int>(m));
	isClean = vector<vector<bool>>(n, vector<bool>(m, false));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &board[i][j]);
		}
	}

	//////////////////

	int answer = 0;
	bool isOver = false;

	while (true) {
		//1) 현재 위치 청소
		isClean[row][col] = true;
		answer++;

		int check = 0;
		for (int i = 0; i < 4; i++) {
			if (hasLeftSpace()) {
				rotate();  //회전
				moveForward();  //전진
				
				break;  //1)로 넘어가기
			}

			if (!hasLeftSpace()) {
				//왼쪽에 청소할 공간 없다면
				check++;
				rotate();
			}

			if (check == 4) {
				//네방향 다 없어
				if (!hasBackSpace()) {
					//뒤쪽 방향이 벽
					isOver = true;  //while 탈출
					break;  
				}

				moveBack();  //한칸 후진
				check = 0;
				i = -1;  //다시 네방향 처음부터 검사
			}
		}

		if (isOver)
			break;
	}

	printf("%d\n", answer);
	return 0;
}

 

시뮬

주의해야 할 점: 청소기 방향에 따라서 오른쪽 왼쪽 앞 뒤 좌표값을 다르게 줘야한다

 

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

14503번: 로봇 청소기