[BOJ/C++] 백준 14503번: 로봇 청소기

 

🔗 문제 링크 : https://www.acmicpc.net/problem/14503

 

 

☁ 로봇 청소기 감시하기

로봇 청소기의 작동 방식 그대로 코드로 구현하면서, 술술 풀리는 줄 알았지만.. 테스트 케이스 2번에서 문제가 터지고 11 x 10 사이즈의 맵에서의 디버깅을 시작하였다. 

청소하는 경로를 추적하는 방법은 문제해결에 아주아주 큰 도움이 된다.

간절한 분에게 비교문서로서 도움 되길 바라며.. 이 본문의 마지막 부분에 테스트케이스 2번의 정상적인 청소 경로를 포함하였다. 

 

참고로 테스트 케이스 2번의 결과는 모든 빈칸을 청소한 결과가 아니다.

즉, 청소되지 않은 칸이 존재한다.

 

 

나의 로봇 청소기.jpg

 

나의 망가진 로봇 청소기의 경로는 기가막혔다. 

 

 

---

 

문제

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

로봇 청소기가 있는 방은 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번으로 돌아간다.

 

 

 

 

 

입출력 예시

입력

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

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

 

 

출력

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

 

 

 

입출력 예시

 

 

 

---

 

풀이 

❗ 주의할 점 ❗

문제로 제시된 로봇청소기의 작동원리에서 "1번으로 돌아간다"라는 말이.. 맨 처음 1번인 "(1)현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다." 이 과정으로 돌아가는 줄 알고 이해가 안 되어서 30분 넘게 문제만 노려봤다..

(3-3)의 1번으로 돌아가라는 말은 (1)이 아닌 (3-1)임을 알아두자.

 

로봇 청소기가 현 위치에서 주변을 탐색하는 부분은 BFS로 해결하였다.

문제의 조건에서 "(2)현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우, (2-1)바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다."라는 부분을 처리하면서 재귀도 사용해 볼 만하다는 생각이 들었다.

하지만 일단 아래 코드는 재귀를 사용하지 않았고, 추후에 재귀를 곁들인 DFS로 해결해보려고 한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Pos {
    Pos (int x, int y) {
        this->x = x;
        this->y = y;
    }
    int x;
    int y;
};

int main() {
    ios_base::sync_with_stdio(0);
    int dirX[4] = {-1, 0, 1, 0};
    int dirY[4] = {0, 1, 0, -1};   // 0북, 1동, 2남, 3서
    int count = 0;
    int N, M, r, c, d;
    cin >> N >> M;      // 세로, 가로
    cin >> r >> c >> d; // 시작 좌표 (r, c), 방향
    vector<vector<int>> room(N, vector<int>(M, 0));
    vector<vector<int>> visited(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> room[i][j];
        }
    }

    /* Start */
    queue<Pos> q;
    q.push(Pos(r, c));

    int n = 1;
    while(!q.empty()) {
        Pos curr = q.front();
        q.pop();
        /* 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. */
        if (visited[curr.x][curr.y] != 1) {
            visited[curr.x][curr.y] = 1;
            count++;
        }
        
        /* 주변 4칸 탐색 */
        bool isAllCleaned = true;
        for (int dir = 0; dir < 4; dir++) {
            int nx = curr.x + dirX[dir];
            int ny = curr.y + dirY[dir];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (visited[nx][ny] || room[nx][ny] == 1) continue;

            /* 주변 4칸 중 청소되지 않은 빈칸이 있는 경우 */
            isAllCleaned = false;
            for (int i = 0; i < 4; i++) {
                d = (d + 3) % 4; // 반시계방향으로 90도 회전
                int fx = curr.x + dirX[d];
                int fy = curr.y + dirY[d];
                if (visited[fx][fy] || room[fx][fy] == 1) continue;
                q.push(Pos(fx, fy));
                break;
            }
            break;
        }

        /* 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우 */
        if (isAllCleaned) {
            int bx = curr.x + dirX[(d+2)%4];
            int by = curr.y + dirY[(d+2)%4];
            if (room[bx][by] == 1) {
                cout << count;
                return 0;
            }
            q.push(Pos(bx, by));
        }
    }
}

 

반시계 방향으로 90° 회전

❗  주의할 점 ❗

주변에 1. 청소가 안 되었고, 2. 접근이 가능한 빈칸이 존재하면, 반드시 반시계방향으로 90°회전한다.

 

반시계방향 회전은 아래와 같은 로직으로 구현한다.

문제에서 중요한 "시계반대 방향으로 90도 회전"하는 부분은

• ( 현재 바라보고 있는 방향 + 3 ) % 4

이런 식으로 구할 수 있다.

예를 들어, 현재 바라보고 있는 방향이 북(0)일 때, 반시계방향으로 90도 회전한 후의 방향은, (0 + 3) % 4로 서(3)를 구할 수 있다.

같은 방법으로 현재 남(2)을 바라보고 있다면, 회전 후, (2 + 3) % 4 = 동(1)을 바라보게 된다.

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};   // 0북, 1동, 2남, 3서

/* d는 현재 바라보는 방향 */
d = (d + 3) % 4; // 반시계방향으로 90도 회전
int fx = curr.x + dirX[d];
int fy = curr.y + dirY[d];

 

 

 

 

✔ 테스트 케이스 2번 | 청소 진행 경로

TestCase 2번의 결과인 57의 청소 진행 경로는 아래와 같다.

1: 7 4
2: 7 3
3: 8 3
4: 8 4
5: 9 4
6: 9 5
7: 8 5
8: 7 5
9: 6 5
10: 6 4
11: 5 4
12: 5 3
13: 6 3
14: 6 2
15: 7 2
16: 7 1
17: 8 1
18: 8 2
19: 9 2
20: 9 3
21: 9 1
22: 9 6
23: 9 7
24: 9 8
25: 8 8
26: 7 8
27: 6 8
28: 5 8
29: 5 7
30: 4 7
31: 4 6
32: 5 6
33: 5 5
34: 4 5
35: 4 4
36: 3 5
37: 3 6
38: 3 7
39: 3 8
40: 2 8
41: 1 8
42: 1 7
43: 1 6
44: 1 5
45: 1 4
46: 1 3
47: 2 3
48: 2 2
49: 3 2
50: 3 1
51: 4 1
52: 5 1
53: 5 2
54: 6 1
55: 2 1
56: 1 1
57: 1 2

 

---