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

백준의 로봇청소기(14503) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 맵의 가로 , 세로크기와 로봇의 현재위치, 그리고 로봇의 초기 진행방향이 주어진다.

- 맵은 0과 1로 이루어져 있으며 0은 빈칸으로 청소를 할 수 있는 공간이고 1은 벽으로써 청소를 할 수 없는 공간이다.

- 그리고 로봇 청소기가 움직임의 조건이 주어진다.

조건은 위와 같다. 너무 길어서 직접 쓰지는 않겠다....

- 위와 같은 조건으로 로봇 청소기에게 청소를 시켰을 때, 청소할 수 있는 칸의 갯수를 출력시키면 된다.

[ 문제풀이 ]

1. 먼저 이 문제에서 가장 까다로웠던 점이, 그냥 4방향을 둘러보고 청소를 할 수 있는 곳이면 청소를 하러 가는 것이 아닌

   탐색 방향도 조건에 있다는 것이 가장 까다로웠다.

   먼저 문제를 읽고, 방향을(dx[], dy[]) 문제에서 주어진 대로 설정해주었다.

   0 = 북 / 1 = 동 / 2 = 남 / 3 = 서

   dx[] = { -1, 0 , 1, 0} , dy[] = { 0, 1, 0, -1} 이렇게 !

2. 문제에서 주어진 조건대로 진행을 해보았다. 그리고 나는 청소를 이미 한 점을 MAP에서 2로 표시를 해주었다.

3. 초기 상태에서 로봇은 빈 공간에 있으므로 1번 조건부터 구현해주었다.

   1. "현재 위치를 청소한다."

   MAP[x][y] = 2 , Room++ (여기서 x,y는 로봇의 초기위치이고, Room이라는 변수는 청소한 방의 갯수를 Count해주는

   변수로 사용하였다.)

   이후 무한루프 안에서 구현을 하였는데, 무한루프의 종료 조건은 청소기가 작동을 멈추는 조건이다.(밑에서 보충설명)

   2번의 조건을 봐보자. 2번과 2-1)번과 2-2번의 조건을 모두 합쳐서 한마디로 설명하자면

   "현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 4방향을 모두 탐색한다." 라는 말이 된다.

   물론 2-1)번의 조건에 부합시키기 위해 청소하지 않은 곳이라면, 4방향을 모두 탐색하기 전에, 청소를 하러 갈 수도

   있다. 2-3)번과 2-4)번의 조건을 보면 "4방향 모두 청소가 이미 되어있거나 벽인 경우에" 라는 말이 있다.

   즉, 왼쪽방향부터 상하좌우 4방향을 탐색하는데, 4방향 모두 청소를 더 이상 진행할 수 없다는 것을 표시할 수 있는

   무언가가 필요하다. 본인은 이 코드에서 CanNotClean 이라는 int형 변수를 썼으며, 이 변수에는 한 점을 기준으로

   4방향을 탐색하면서, 청소를 할 수 없는 칸에 대해서는 ++를 시켜주었다. 즉, 이 변수의 값이 4라면

   2-3)의 조건과 2-4)의 조건을 부합시키도록 구현했다.

  

   그럼 2-1)과 2-2)의 조건문을 부합하도록 구현해보겠다.

   이 부분을 구현하기 위해서 4번 반복하는 for문을 구현하였으며, 그 for문 안의 구현 내용은

   1. 방향전환. (마음대로 하시면 안되고, 현재 방향을 기준으로 왼쪽방향부터 탐색하셔야 합니다 !)

     - (현재방향 : 전환된방향 = 북 : 서 , 서 : 남 , 남 : 동 , 동 : 북)

   2. 전환한 방향으로 한칸 이동해보기

   3. 그 칸이 청소를 할 수 있는 곳인지 아닌지 판단하기

   4. 청소를 할 수 있는 곳이라면 반복문을 종료시키고, 청소하러 가기.

   5. 그게 아니라면 총 4칸중(한 점을 기준으로 상하좌우 총 4칸) 몇 칸 청소를 못하는지 판단하기

   이렇게 현재 방향을 기준으로 왼쪽방향부터 탐색 하는 것을 구현하였으며, 위에서 말했다 시피, 청소를 할 수 없는 칸에

   대해서는 선언해놓은 변수를 ++ 시켜주었다.

   

   위에서 말한 4번을 보자. "청소를 할 수 있는 곳이라면 반복문을 종료시키고, 청소하러 가기."

   나는 청소를 할 수 있는 곳이다 라는 것을 표시하기 위해서 bool형 변수를 하나 사용했으며, 이 변수의 초기값은 false로

   선언해주었으며, 청소를 할 수 있는 곳이 있다라고 판단되면 이 변수의 값을 true로 바꿔주었다.

   이 후, 청소를 했다는 표시로 MAP의 값을 2로 바꿔주었고, 방향도 전환도 시켜주었다.

 

   여기까지 했다면, 청소를 할 수 있는 곳에 대해서는 구현이 완료되었다. 이제는 청소를 할수 없는 경우에 대해서 생각해보자.

   만약 4방향 다 청소를 할 수 없는 곳이라면, 위에서 말한 변수가 4일 것이다.(청소를 할 수 없는 칸에 대해서는 변수를++시키

   므로)

   본인은 ' 이 변수의 값이 4일 때' 라는 조건문 안에서 2-3)과 2-4)의 조건을 구현하였다.

   2-3)의 조건을 구현하기 위해서 기존의 바라보는 방향을 기억하는 변수를 하나 두었고, 그 방향으로 후진하게 만들었다.

   만약 후진을 벽이라서 더이상 하지 못할 경우 반복문이 종료됨과 동시에 로봇 청소기가 동작을 그만한다는 것을

   구현하였다. 이 부분은 범위를 벗어나거나, MAP의 값이 1인 경우 이 조건들을 만족하면 된다.

   말이 어려워서 그렇지 코드를 보면 쉬울 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
pair<pair<int, int>, int> Robot;
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
void Input()
{
    cin >> N >> M;
    cin >> Robot.first.first >> Robot.first.second >> Robot.second;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }                                                         
    }
}                         
 
int Turn_Direction(int d)
{
    if (d == 0) return 3;
    else if (d == 1) return 0;
    else if (d == 2) return 1;
    else if (d == 3) return 2;
}
 
void Solution()
{
    int x = Robot.first.first;
    int y = Robot.first.second;
    int d = Robot.second;
    int Room = 0;
    MAP[x][y] = 2;
    Room++;
 
    int nx, ny, nd;
 
    while (1)
    {
        int Tmp_d = d;
        bool Can_Clean = false;
        int CanNotClean = 0;
        for (int i = 0; i < 4; i++)        // 왼쪽방향으로부터 4방향 차례대로 탐색
        {
            nd = Turn_Direction(d);
            nx = x + dx[nd];
            ny = y + dy[nd];
            
            if (MAP[nx][ny] == 0)
            {
                Can_Clean = true;
                break;
            }
            else if (MAP[nx][ny] == 1 || MAP[nx][ny] == 2 || (nx < 0 || ny <0 || nx >=N || ny >=M))
            {
                d = nd;
                CanNotClean++;
            }
        }
 
        if (Can_Clean == true)
        {
            MAP[nx][ny] = 2;
            Room++;
            d = nd;
        }
 
        if (CanNotClean == 4)
        {
            nx = x - dx[Tmp_d];
            ny = y - dy[Tmp_d];
            d = Tmp_d;
            if ((nx < 0 || ny < 0 || nx >= N || ny >= M) || MAP[nx][ny] == 1 )
            {
                break;
            }
        }
        x = nx;
        y = ny;
    }
    cout << Room << endl;
}                                                                                       
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}