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

문제

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

---

문제 요약

로봇 청소기가 있는 방은 N × M 크기의 직사각형 좌표로 나타낼 수 있다.

 

방의 각 칸은 벽 또는 빈 칸이고, 청소기는 바라보는 방향(동, 서, 남, 북)이 있다.

 

로봇 청소기는 다음과 같이 작동한다.

 

1. 현재 칸이 아직 청소되지 않은 경우

- 현재 칸을 청소한다.

 

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

- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면, 한 칸 후진하고 1번으로 돌아간다.

- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면, 작동을 멈춘다.

 

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

- 반시계 방향으로 90도 회전한다.

- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한ㄷ나.

- 1번으로 돌아간다.

 

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

---

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int n, m, cnt;
int start_x, start_y;

// 북(0), 동(1), 남(2), 서(3)
int dir;

int board[55][55];
bool visited[55][55];

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

bool dfs(int x, int y, int dir) {
    // 현재 칸 청소 (방문 체크)
    if (!visited[x][y]) {
        visited[x][y] = true;
        cnt++;
    }

    // 주변 1칸 중 청소되지 않은 빈칸 여부 확인
    int tmp_d = dir;
    for (int i = 1; i <= 4; i++) {
        tmp_d = (tmp_d + 3) % 4;

        int nx = x + dx[tmp_d];
        int ny = y + dy[tmp_d];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

        if (board[nx][ny] == 1) continue;

        if (visited[nx][ny]) continue;


        if (!dfs(nx, ny, tmp_d)) {
            return false;
        }

        return true;
    }

    // 후진
    int px = x - dx[dir];
    int py = y - dy[dir];

    if (px < 0 || px >= n || py < 0 || py >= m) return false;
    if (board[px][py] == 1) return false;

    return dfs(px, py, dir);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    cin >> start_x >> start_y >> dir;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    if (board[start_x][start_y] == 0) {
        visited[start_x][start_y] = true;
        cnt++;
    }

    dfs(start_x, start_y, dir);
    
    cout << cnt;

    return 0;
}

---

고찰

재귀를 이용하여, 시뮬레이션을 구현하였다.

 

사실 반복문을 통해 코드를 작성하는 것이 더 가독성이 좋고, 깔끔할 것 같다.

 

함수 이름은 dfs이지만, 로봇 청소기가 멈추면 재귀를 멈추어야 한다.따라서, 실제로 깊이 우선 탐색처럼 진행되지는 않는다.(false 반환은 로봇 청소기가 멈추었다는 것을 의미한다.)

 

또, 방향이 북(0), 동(1), 남(2), 서(3)으로 정해져 있으므로, dx/dy 배열을 신경써서 만들어야 편하다.