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

로봇 청소기(Gold 5)

문제

전체 문제 보기

14503번: 로봇 청소기

접근법

이번 문제는 지문에서 요구한 로봇 청소기의 기능을 하나씩 구현하여 시뮬레이션하는 문제입니다. 자칫 DFS로 착각할 수 있는데 지문에서 요구한 로봇의 움직임은 DFS와 다르기 때문에 다른 결과가 나옵니다. 그래서 지문에 나온 로봇청소기의 동작을 정확하게 구현하는 것이 중요합니다. 지문에 제시된 로봇 청소기의 기능들을 클래스로 다음과 같이 추상화할 수 있습니다.

using Level = vector<vector<int>>;
struct Pos {
    Pos() {}
    Pos(int _r, int _c) : r(_r), c(_c) {}
    int r{};
    int c{};
};
class Robot {
public:
    Robot(Level& _level, Pos _pos, int _dir);
    void MoveForward();  // 앞으로 이동
    bool MoveBackward(); // 뒤로 이동 (뒤에 벽이 있을 경우 false 반환)
    void RotateLeft();   // 왼쪽 방향으로 회전
    void Clean();        // 현재 위치 청소
    bool Search();       // 바라보고 있는 방향이 0인지 확인
    Pos GetPos() const { return pos; }
    int GetCleanCnt() const { return cleanCnt; }
private:
    Level& level;
    Pos pos;
    int dir;
    int cleanCnt{};
    const int dr[4]{ -1,0,1,0 };
    const int dc[4]{ 0,1,0,-1 };
};

지문에서 로봇청소기의 동작 순서를 다음과 같이 설명하고 있습니다.

• 현재 위치를 청소한다.
• 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
  • 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
  • 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
  • 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  • 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

이를 앞서 정의한 로봇 청소기의 기능들을 활용하여 아래와 같이 로직을 구현할 수 있습니다.

    while (1)
    {
        // (청소할 수 있다면) 현재 위치를 청소한다.
        Pos cur = robot.GetPos();
        if(level[cur.r][cur.c] == 0)
            robot.Clean();

        bool Search{};
        // 현재 방향을 기준으로 왼쪽 방향 부터 차례대로 인접한 칸들을 탐색한다.
        for(int i = 0; i < 4; ++i)
        {
            robot.RotateLeft();
            if (robot.Search()) 
            {
                // 청소할 공간이 존재한다면 전진후 처음 부터 다시 진행한다.
                robot.MoveForward();
                Search = true;
                break;
            }
        }
        // 4방향 모두 청소 할 수 없는 경우 뒤로 이동한다
        if (Search == false)
        {
            // 뒤로 이동 할 수 없을 경우 청소 종료
            if (robot.MoveBackward() == false)
                break;
        }
    }

전체 구현

앞서 설명한 로봇 청소기의 기능들을 아래와 같이 모두 구현하면 답을 계산할 수 있습니다.

#include <stdio.h>
#include <vector>
using namespace std;

using Level = vector<vector<int>>;
struct Pos {
    Pos() {}
    Pos(int _r, int _c) : r(_r), c(_c) {}
    int r{};
    int c{};
};
class Robot {
public:
    Robot(Level& _level, Pos _pos, int _dir);
    void MoveForward();
    bool MoveBackward();
    void RotateLeft();
    void Clean();
    bool Search();
    Pos GetPos() const { return pos; }
    int GetCleanCnt() const { return cleanCnt; }
private:
    Level& level;
    Pos pos;
    int dir;
    int cleanCnt{};
    const int dr[4]{ -1,0,1,0 };
    const int dc[4]{ 0,1,0,-1 };
};
Robot::Robot(Level& _level, Pos _pos, int _dir) : level(_level), pos(_pos), dir(_dir)
{

}
void Robot::MoveForward()
{
    pos.r += dr[dir];
    pos.c += dc[dir];
}
bool Robot::MoveBackward()
{
    pos.r -= dr[dir];
    pos.c -= dc[dir];
    if (level[pos.r][pos.c] == 1)
        return false;

    return true;
}
void Robot::RotateLeft()
{
    dir = (dir + 3) % 4;
}
void Robot::Clean()
{
    level[pos.r][pos.c] = 2;
    cleanCnt++;
}
bool Robot::Search()
{
    int nextR = pos.r + dr[dir];
    int nextC = pos.c + dc[dir];

    if (level[nextR][nextC] == 0)
        return true;

    return false;
}
int main() {

    int N, M; // N, M  (3 ≤ N, M ≤ 50)
    scanf("%d %d ", &N, &M);
    int r, c, d; // d (0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽)
    scanf("%d %d %d ", &r, &c, &d);

    Level level(N);
    for (int i = 0; i < N; ++i)
    {
        level[i].resize(M);
        for (int j = 0; j < M; ++j)
        {
            scanf("%d ", &level[i][j]);
        }
    }

    Robot robot(level, Pos(r, c), d);

    while (1)
    {
        Pos cur = robot.GetPos();
        if(level[cur.r][cur.c] == 0)
            robot.Clean();

        bool Search{};

        for(int i = 0; i < 4; ++i)
        {
            robot.RotateLeft();
            if (robot.Search()) 
            {
                robot.MoveForward();
                Search = true;
                break;
            }
        }
        // 4방향 모두 청소 할 수 없는 경우
        if (Search == false)
        {
            // 뒤로 이동 할 수 없을 경우 청소 종료
            if (robot.MoveBackward() == false)
                break;
        }
    }
    printf("%d\n", robot.GetCleanCnt());

    return 0;
}