[백준 14503] 로봇 청소기 (C++)

A. 문제설명

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

문제에 대한 자세한 설명은 링크 참조

 

1. 로봇 청소기가 방 안을 청소

2. 방은 N*M 크기의 배열로 되어있으며 벽이 있는 공간은 청소할 수 없음

3. 로봇청소기는 먼저 현재 위치를 청소하고

3-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진

3-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전

3-3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진

3-4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춤

4. 최종적으로 청소기가 동작을 멈출 때, 청소한 칸의 갯수를 구하라

 

B. 접근법

시뮬레이션

 

3번의 로봇 청소기의 동작을 충실히 알고리즘으로 구현하여 청소를 못하는 조건이 올 때까지 무한루프 안에서 동작

 

C. 풀이

1. 로봇 청소기가 종료조건이 될 때까지 무한루프 안에서 청소를 반복

2. 로봇 청소기의 탐색 알고리즘 적용, 종료 조건시 무한루프 탈출

3. 청소된 칸의 갯수를 계수

 

D. 내 코드

	#include <iostream>
	using namespace std;
	int N, M;
	bool arr[50][50] = {0, }; // 0:빈칸, 1:벽
	bool clean[50][50] = {0, }; // 0:청소안됨 1:청소됨
	int dir = 0; // 0:↑, 1:→, 2:↓, 3:←
	// 현재 방향의 왼쪽은 (dir+3)%4
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, 1, 0, -1};
	int x, y; // 로봇의 좌표
	bool vacuum(){
	clean[x][y] = true;
	//현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색
	for (int i = 0; i < 4; i++) {
	//왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진
	dir = (dir + 3) % 4;
	if(!arr[x+dx[dir]][y+dy[dir]] && !clean[x+dx[dir]][y+dy[dir]]) {
	x += dx[dir];
	y += dy[dir];
	return false; // 청소가 안끝났을 시 false 반환
	}
	}
	//네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진
	int backDir = (dir + 2) % 4;
	if(!arr[x+dx[backDir]][y+dy[backDir]]){
	x += dx[backDir];
	y += dy[backDir];
	return false; // 청소가 안끝났을 시 false 반환
	}
	//네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
	return true;
	}
	int main(){
	cin >> N >> M;
	cin >> x >> y >> dir;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	cin >> arr[i][j];
	}
	}
	bool end;
	do{
	end = vacuum();
	} while(!end);
	int cnt = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if(clean[i][j]) cnt++;
	}
	}
	cout << cnt << endl;
	return 0;
	}

view raw vacuum.cpp hosted with ❤ by GitHub