[ baekjoon ] #14503 로봇청소기

백준 #14503 로봇청소기

문제 요약

---

• 로봇 청소기가 있는 방은 NxM 크기의 직사각형으로 나타낼 수 있다.
• 각각의 칸은 벽 or 빈 칸
• 청소기는 바라보는 방향이 있다. (동, 서, 남, 북)
• 청소기 작동 규칙
  1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸 청소
  2. 현재 칸의 주변 4칸이 다 청소된 경우,
     → 바라보는 방향을 유지한 채로 한 칸 후진 할 수 있다면 한 칸 후진 후 1번으로 돌아가기
     → 후진할 수 없다면 작동 멈춤
  3. 현재 칸의 주변 4칸 중 빈 칸이 있는 경우,
     → 반시계 방향으로 90˚ 회전
     → 바라보는 방향 기준 앞칸이 청소되지 않은 빈 칸인 경우 한 칸 전진
     → 1번으로 돌아감

💡Idea

1. 청소가 된 곳인지 어떻게 판단할까?
   → 방 상태는 청소되지 않은 빈칸(0)과 벽(1)으로 구분되어있다.
   → 청소된 곳도 1로 바꿔주자
2. 후진은 어떻게 할까?
   → 현재 방향의 값을 빼주자
3. 반시계 방향으로 90도 회전을 어떻게 할까?

• d의 값이 0이라면 북쪽, 1이라면 동쪽, 2라면 남쪽, 3이라면 서쪽이다.
  → dir을 북, 동, 남, 서로 해두고 d의 값을 하나씩 줄이자
  → d가 음수가 될 경우는 북(0)일 경우 뿐이므로 d를 3으로 지정하자

[ SourceCode ]

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

int N, M, d; // 방의 세로, 가로 크기, 로봇 청소기 방향
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 북 동 남 서 (시계 방향)
queue <pair<int, int>> cleaning;

void clean_room(vector <vector<int>> &room) {
    int cnt = 0;
    while(!cleaning.empty()) {
        int x = cleaning.front().first;
        int y = cleaning.front().second;
        cleaning.pop();

        // 1. 현재 칸 청소되지 않은 경우 청소하기
        if(room[x][y] == 0) {
            room[x][y] = -1;
            cnt++;
        }

        bool dirty = false;
        for(int i=0; i<4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
           
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(room[nx][ny] == 0) {
                dirty = true;
                break;
            }
        }

        // 2. 청소되지 않은 곳이 없는 경우
        if(!dirty) {
            int nx = x - dir[d][0];
            int ny = y - dir[d][1];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M || room[nx][ny] == 1) break;
            if(room[nx][ny] != 1) cleaning.push({nx, ny}); // 벽이 아니라면
        }

        // 3. 청소되지 않은 곳이 있는 경우
        else {
            d--; // 반시계 방향 90도 회전
            if(d < 0) d = 3;
            int nx = x + dir[d][0];
            int ny = y + dir[d][1];
            if(room[nx][ny] == 0) {
                cleaning.push({nx, ny});
            }
            else cleaning.push({x, y});
        }
    }

    cout << cnt;
}

int main() {
    // 1. 입력 받기
    cin >> N >> M;
    int r, c; // 로봇 청소기 위치
    cin >> r >> c >> d;
    vector <vector<int>> room(N, vector<int>(M));
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> room[i][j];
        }
    }

    // 2. 청소하기
    cleaning.push({r, c});
    clean_room(room);

    return 0;
}

Feedback

---

1. 청소한 칸을 벽으로 바꿔주는 부분이 문제였다.
   → 벽으로 바꾸게 되면 후진을 할 수 없게 되는 문제가 발생한다 ㅠㅠ
   → 귀찮아도 시뮬레이션 끝까지 한 번 해보기 !!
2. 주석을 달고 함수를 분리하는 습관이 든 것 같아서 만족한다