백준 : 14503 로봇 청소기(c++)

백준 링크

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

14503번: 로봇 청소기

문제 설명

코드 풀이

1. 큐에 처음 로봇의 위치를 넣어준다.

2. 로봇이 위치한 구역이 청소가 안 되어 있다면 청소한다.

3 - 1. 4방향에 위치한 칸 중 청소가 안 되어있는 칸이 있다면 반시계 방향으로 90도 회전 후 전진한다. 이후 2번으로 빽

3 - 2.a 4방향 모두 청소가 되어있거나 벽이라면 방향을 유지한 채로 뒤로 한 칸 후진하고 다시 2번으로 빽

3 - 2.b 뒤로 후진 할 때 뒤에가 벽이라면 종료

 

2번 테스트 케이스 순서

BFS 코드(실패)

#include <iostream>
#include <queue>


using namespace std;

int Board[51][51];
//int Dist[51][51];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N, M;   // N = 세로, M = 가로
int Count;  // 청소 할 수 있는 총 구역의 개수
pair<int, int> RobotDir;
int Direction;

enum DIR_ENUM
{
    North,
    East,
    South,
    West
};

void DirConvert(int _Dir)
{
    switch (DIR_ENUM(_Dir))
    {
    case North:
        RobotDir.first = -1;
        RobotDir.second = 0;
        break;
    case East:
        RobotDir.first = 0;
        RobotDir.second = 1;
        break;
    case South:
        RobotDir.first = 1;
        RobotDir.second = 0;
        break;
    case West:
        RobotDir.first = 0;
        RobotDir.second = -1;
        break;
    }
}

int main(void)
{
    int Y, X;
    cin >> N >> M;
    cin >> Y >> X >> Direction;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> Board[i][j];

            /*if (Board[i][j] == 0)
                Dist[i][j] = -1;*/
        }
    }

    queue<pair<int, int>> qPair;

    ++Count;
    qPair.push({ Y, X });
    //Dist[Y][X] = Count;
    Board[qPair.front().first][qPair.front().second] = 2;
    DirConvert(Direction);

    while (!qPair.empty())
    {
        pair<int, int> Cur = qPair.front();
        qPair.pop();

        bool Enable = false;

        for (int Dir = 0; Dir < 4; ++Dir)
        {
            int NextX = Cur.second + dx[Dir];
            int NextY = Cur.first + dy[Dir];

            if (NextX < 0 || NextY < 0 || NextX >= M || NextY >= N)
                continue;

            if (Board[NextY][NextX] != 0)
                continue;
            
            Enable = true;
        }

        // Enable 이 활성화가 안되어 있다면 현재의 위치에서 상하좌우 전부 청소가 되어 있다는 의미이다 그래서
        // 2번의 조건에 의해 바라보는 방향을 유지한 채로 한 칸 뒤로 후진하고 청소하고 뒤에 벽이 있을때까지 반복한다
        if (!Enable)
        {
            // 후진 해야되기 때문에 -1 곱해준다
            int NextX = Cur.second + RobotDir.second * -1;
            int NextY = Cur.first + RobotDir.first * -1;

            if (NextX < 0 || NextY < 0 || NextX >= M || NextY >= N)
                break;
            
            if (Board[NextY][NextX] == 0)
            {
                qPair.push({ NextY, NextX });
                ++Count;
                Board[NextY][NextX] = 2;
                //Dist[NextY][NextX] = Count;
            }
            else if(Board[NextY][NextX] == 2)
            {
                qPair.push({ NextY, NextX });
            }
            else if (Board[NextY][NextX] == 1)
            {
                break;
            }

        }

        // Enable이 활성화 상태라면 현재의 위치에서 상하좌우 중 한 공간은 청소가 안 되어 있는 공간이다
        // 그래서 반시계 방향으로 90도 회전한다.
        // 이때  바라보는 기준으로 앞쪽 칸이 청소가 되어 있지 않다면 앞으로 한 칸 전진하고 1번으로 돌아간다.
        // 만약 바라보는 기준 앞쪽 칸이 청소가 되어있지 않다면 다시 90도만큼 회전후 재 탐색
        else
        {
            Direction -= 1;

            if (Direction < 0)
                Direction = 3;

            // 방향을 얻어온다.
            DirConvert(Direction);

            int NextX = Cur.second + RobotDir.second;
            int NextY = Cur.first + RobotDir.first;

            if (NextX < 0 || NextY < 0 || NextX >= M || NextY >= N)
                continue;

            // 다음 칸이 청소되어 있다면 다시 90도만큼 회전해야한다.
            while (Board[NextY][NextX] != 0)
            {
                Direction -= 1;

                if (Direction < 0)
                    Direction = 3;

                // 방향을 얻어온다.
                DirConvert(Direction);

                // 회전한 방향이 범위 밖이라면 continue
                if (Cur.second + RobotDir.second < 0 || Cur.first + RobotDir.first < 0 || Cur.second + RobotDir.second >= M
                    || Cur.first + RobotDir.first >= N)
                    continue;

                NextX = Cur.second + RobotDir.second;
                NextY = Cur.first + RobotDir.first;

            }

            // 여기로 왔다면 다음칸으로 갈 수 있다는 의미이다.
            ++Count;
            Board[NextY][NextX] = 2;
            //Dist[NextY][NextX] = Count;
            qPair.push({ NextY, NextX });
        }
    }

    /*std::cout << '\n';
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            std::cout << Dist[i][j] << '\t';
        }
        std::cout << '\n';
    }*/

    std::cout << Count;

    return 0;
}

---

Dist관련 주석 해제하면 탐색 순서 확인 가능

 

테스트 케이스 반례 공유

https://www.acmicpc.net/board/view/67476

글 읽기 - [로봇 청소기] 테스트 케이스(반례) 공유합니다.