1) 문제 분석
문제에서 하라는대로만 코드를 작성하면 쉽게 해결될 것 처럼 보였다. 실제로 정답률도 50퍼센트가 넘을 정도로 높다.
-필요한 사항
- 청소한 칸인지 아닌지 알아야 함: 청소한 구역은 -1로 저장하자
- 청소한 칸의 개수를 세야함: count 변수 사용
- N*M 크기의 int 2차원 배열이 필요함 (청소 구역 나타내기 위해)
- 로봇 청소기는 현재 위치와 방향을 알고 있어야 함 => 클래스?
- 탐색을 시작할 때 마다 2차원 배열과 현재 위치, 방향만 참고하면 됨
2) 알고리즘
로봇 청소기 class
class Robot_V{
//current position
int r, c;
//current direction
int dir;
//space the vacuum is cleaning
int** space;
//size of the space
int N, M;
//number of blocks cleaned
int count;
로봇 청소기 클래스의 인스턴스를 생성하고, 청소할 공간에 대한 정보를 넘겨준 뒤, 로봇 청소기의 현재 위치를 세팅한다. 그 다음, start_cleaning()이라는 멤버 함수를 호출하면, 이 함수가 청소하는 작업을 내부적으로 수행한 다음, 청소한 칸들의 개수를 리턴해준다.
3) 코드
#include <iostream>
#include <string>
using namespace std;
//enumeration type of directions
enum direction{north=0, east=1, south=2, west=3};
//robot vacuum class
class Robot_V{
//current position
int r, c;
//current direction
int dir;
//space the vacuum is cleaning
int** space;
//size of the space
int N, M;
//number of blocks cleaned
int count;
public:
//initialize
Robot_V(){
r = c = 0;
dir = north;
count = 0;
}
//set data of the space to be cleaned
void set_space(int** s, int n, int m){
space = s;
N = n; M = m;
}
//set position of the robot
void set_position(int R, int C, int d){
r = R; c = C;
dir = d;
}
//clean the place and return the number of blocks cleaned
int start_cleaning(){
bool found = true;
while(true) {
//clean current postion
if(found) {
space[r][c] = -1;
count++;
}
//search new spot to clean
found = search_spots();
//if it fails at finding new spot to clean
if(!found){
//move backwards and if failed, stop cleaning
if(!move_back())
break;
}
}
return count;
}
private:
//search for next block to clean
bool search_spots(){
for(int i=0 ;i<4; i++){
//change the direction to the left
dir = (dir+3)%4;
//search north
if(dir==north && r-1>=0 && space[r-1][c]==0){
r -= 1;
return true;
}
//search west
else if(dir==west && c-1>=0 && space[r][c-1]==0){
c -=1;
return true;
}
//search south
else if(dir==south && r+1<N && space[r+1][c]==0){
r+=1;
return true;
}
//search east
else if(dir==east && c+1<M && space[r][c+1]==0){
c+=1;
return true;
}
}
//failed to find a next block to clean
return false;
}
//check if the robot can move one block backwards or not
bool move_back(){
switch(dir){
case north:
if(r+1<N && space[r+1][c]!=1) {
r += 1;
return true;
}
break;
case west:
if(c+1<M && space[r][c+1]!=1){
c += 1;
return true;
}
break;
case south:
if(r-1>=0 && space[r-1][c]!=1){
r-=1;
return true;
}
break;
case east:
if(c-1>=0 && space[r][c-1]!=1){
c-=1;
return true;
}
}
//cannot move backwards
return false;
}
};
int main(){
Robot_V robot; //robot vacuum
int ** room; //state of the place to clean
int n, m; //size of the place to clean
int x, y, d; //position of the robot (x:r, y:c, d:direction)
int s;
//initialize space to clean, the space is divided into n*m blocks
cin >> n; cin >> m;
room = new int*[n];
for(int i=0; i<n; i++)
room[i] = new int[m];
//get current position of the robot from input
cin >> x; cin >> y; cin >> d;
//get current state of the space to clean
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> s;
room[i][j] = s;
}
}
//set position of the robot and space to be cleaned
robot.set_position(x,y,d);
robot.set_space(room, n, m);
//start cleaning the space
int total = robot.start_cleaning();
//print out number of blocks cleaned
cout << total;
}