14503 로봇청소기

현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,

바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,

반시계 방향으로 90도 회전한다.
바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
1번으로 돌아간다.

5 5 2 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1

좀 어려웠다. 일단

이동 전에 현재 바라보는 방향에서 90도 회전을 시켜줘야 하는 점

Count를 후진할 땐 올려주지 않아야 한다는 점 3.

0,0 ~ N-1,M-1 즉 5x5 라면 4,4 가 맨 마지막이란 소리가 좀 잘 이해가 안 되었던 것 같다.

그래도 반례를 좀 뒤져보기도 했고, 직접 손으로 로봇청소기 경로를 따라가다 보니 원 큐에 정답처리 되어 기쁘다


#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>

using namespace std;
#define MAX 51
enum dir {
    North =0, //북
    East = 1,    // 동
    South = 2, // 남
    West = 3 // 서
};
int N, M;
int MAP[MAX][MAX];
bool visited[MAX][MAX] = { false };
struct point {
    int ry, cx;
};
point start;
int curdir;
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};
int Count = 0;
void Input()
{
    cin >> N >> M;
    cin >> start.ry >> start.cx >> curdir;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
bool Serach(pair<int, int> s)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = s.first + dr[i];
        int nx = s.second + dc[i];
        if (ny >= 0 && ny < N && nx >= 0 && nx < M)
        {
            //만약 해당 칸이 아직 청소 전 이고 벽이 아니라면 곧바로 false를 뱉어줌.
            if (visited[ny][nx] == false && MAP[ny][nx] == 0) return false;
        }
    }
    //예외조건에 맞지 않으면, 4방향 모두 청소가 되었거나, 벽이 있는 경우.
    return true;
}
void DFS(pair<int, int> here)
{

    visited[here.first][here.second] = true;
    if (Serach(here))
    {
        //curdir를 기준의 반대방향으로 갈 수 있는지 마지막으로 체크하고 아니라면 끝내줘야함
        int dir = (curdir + 2) % 4;
        int by = here.first + dr[dir];
        int bx = here.second + dc[dir];
        // 뒷 방향이 벽인지 아닌지 체크.
        if (by >= 0 && by < N && bx >= 0 && bx < M && MAP[by][bx] == 0)
        {
            DFS({ by,bx });
        }
        // 분기에 들어오지 않으면 작동멈춤
    }
    else {
        // 청소할 곳을 찾았을 때 
        // 1. 반시계 방향으로 회전한다.
        for (int i = 0; i < 4; i++)
        {
            curdir = (curdir + 3) % 4;
            int ny = here.first + dr[curdir];
            int nx = here.second + dc[curdir];
            // 앞으로 나아갈 방향이 청소전이고, 벽이 아니라면 이동
            if (visited[ny][nx] == false && MAP[ny][nx] == 0)
            {
                Count++;
                DFS({ ny,nx });
                //DFS 이후 꺼줌
                return;
            }
            //다 돌았는데 DFS가 실행안 되면 청소 모두 완료.
        }
 
    }
}
void Solution()
{
    DFS({ start.ry,start.cx });
    cout << Count+1 << '\n';
}

void Solve()
{
    Input();
    Solution();

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();
}