14503>로봇 청소기

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

 

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 N X M 크기의 직사각형으로 나타낼 수 있으며, 1 X 1 크기의 정사각형 칸으로 나누어져 있다.
각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0) 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r,c) 는 북쪽에서 (r + 1)번째에 있는 줄의 서쪽에서 (c + 1)번째 칸을 가리킨다.

처음에 빈 칸은 전부 청소되지 않은 상태이다. 로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

 

#include <iostream>
#include<memory.h>

int N, M;
int r[50][50];
int v[50][50];

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

int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int count = 0;
bool DFS(int x, int y, int d)
{
    //std::cout << y << "," << x  << std::endl;
    if (v[y][x] == 0)
    {
        v[y][x] = 1;
        count++;
    }
    for (int i = 0; i < 4; ++i)
    {
        int nd = (d + 3 - i) % 4;
        int nx = x + dx[nd];
        int ny = y + dy[nd];

        if (r[ny][nx] == 0 && v[ny][nx] == 0)
        {
            v[ny][nx] = 1;
            count++;
            if (DFS(nx, ny, nd) == false)
                return false;
        }
    }
    int bd = (d + 2) % 4;
    int bx = x + dx[bd];
    int by = y + dy[bd];
    if (r[by][bx] == 0)
    {
        if (DFS(bx, by, d) == false)
            return false;
    }
    else if(r[by][bx] == 1)
        return false;
    return true;
}
int main()
{
    std::ios::ios_base::sync_with_stdio(false);
    memset(r, -1, sizeof(r));

    std::cin >> N >> M;

    int x, y, d;

    std::cin >> y >> x >> d;

    for (int i = 0; i < N; ++i)
    {
        for (int ii = 0; ii < M; ++ii)
        {
            std::cin>> r[i][ii];
        }
    }
    DFS(x, y, d);
    std::cout << count;
}

 

이동하는 모습을 디버깅해보면서 풀면 된다.