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

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기 작동방식
1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우,

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

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

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

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

입력

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 $N$개의 줄에 각 장소의 상태를 나타내는 $N \times M$개의 값이 한 줄에 $M$개씩 입력된다. $i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태를 나타내며, 이 값이 $0$인 경우 $(i, j)$가 청소되지 않은 빈 칸이고, $1$인 경우 $(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

풀이

일반적인 탐색문제에서 방향이 추가된 문제로, 탐색에 있어 방향을 고려해야 한다.
문제 조건 중 탐색 방향을 반시계 방향으로 $90^\circ$회전할 때가 있는데, 현재 방향에 대하여 회전이므로 일일이 if문으로 확인하기에 복잡하다. 해당 방향으로 전진하는 경우를 dx dy 배열로 담고, 이를 인덱스로 잡는다.

0 : 북 (-1,0)
1 : 동 (0,1)
2 : 남 (1,0)
3 : 서 (0,-1)

위를 기준으로, 반시계 방향으로 회전한다면

• 북(0) -> 서(3)
• 동(1) -> 북(0)
• 남(2) -> 동(1)
• 서(3) -> 남(2)

이고, 북(0)일 경우에만 3, 제외한 나머지 방향은 현재 방향에서 -1 하면 된다.
다른 블로그에선 나머지 연산을 이용하여 계산하였는데, 방향이 들어가는 문제는 나머지 연산을 이용해서 푸는게 깔끔하고 좋은 것 같다.

#include <iostream>

using namespace std;

int n, m, r, c, d, answer, dis, nx, ny, nd;
int map[50][50];
//북, 동, 남, 서
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool check(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 0)
        {
            return false;
        }
    }
    return true;
}
void dfs(int x, int y, int d)
{
    if (map[x][y] == 1 || dis == 1)
    {
        return;
    }
    if (map[x][y] == 0)
    {
        answer++;
        map[x][y] = 2;
    }

    if (check(x, y))
    {
        // int nd = (d + 2) % 4;
        d > 1 ? nd = d - 2 : nd = d + 2;
        nx = x + dx[nd];
        ny = y + dy[nd];
        if (map[nx][ny] == 1)
        {
            dis = 1;
            return;
        }
        dfs(nx, ny, d);
    }

    else
    {
        nd = d;
        for (int i = 0; i < 4; i++)
        {
            // nd = (nd + 3) % 4;
            nd == 0 ? nd = 3 : nd -= 1;
            nx = x + dx[nd];
            ny = y + dy[nd];
            if (map[nx][ny] == 0)
            {
                dfs(nx, ny, nd);
                break;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    cin >> r >> c >> d;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
    dfs(r, c, d);

    cout << answer << '\n';
    return 0;
}