[Gold 5] 14503 로봇 청소기

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

 

이 문제는 BFS와 유사한 방식으로 해결하였다.

 

우선, 로봇 청소기는 주변의 4개의 칸에 대해 움직일 수 있으면 시계 반대 방향으로 회전한다.

하지만 로봇 청소기의 현재 방향을 가리키는 변수 d의 값은 시계 방향으로 흘러간다.

따라서 dy, dx 배열에 시계 반대 방향으로 이동 방향을 결정해준다.

int r, c, d; // 0 : 북, 1 : 동, 2 : 남, 3 : 서
int dy[4] = {-1, 0, 1, 0}; // 북, 서, 남, 동
int dx[4] = {0, 1, 0, -1};

 

방에 있는 로봇 청소기의 현재 위치가 벽일 경우 이동을 멈추게 구현하였다.

문제에는 로봇 청소기가 뒤로 이동할 수 없는 경우 이동을 멈추라고 나와있지만

로봇 청소기가 회전하여 앞으로 이동할 경우도 있기 때문에

반복 조건을 현재 위치가 벽이 아닌 경우로 결정하였다.

 

따라서 현재 위치가 0인 경우 (청소한 상태가 아닌 경우)

방 상태를 2(청소한 상태)로 변경하고, 시간을 증가시킨다.

while(room[r][c] != 1){
    if(room[r][c] == 0){
        room[r][c] = 2;
        answer++;
    }
    // 청소기 이동 방식 구현
    ...
}

 

청소기가 이동하는 방식은 d에 의해 결정되도록 하였다.

4회 반복을 통해 이동할 수 없는 경우 원래 방향을 바라보도록 한다.

또한, 시계 반대 방향으로 회전해야 하므로 d를 감소 시킨다.

이때, d가 음수가 되면 서쪽을 바라보도록 한다.

 

청소기의 현재 위치에 따라 청소기가 이동할 다음 칸을 결정시킨다.

즉, 청소기의 다음 이동칸이 청소할 칸인 경우 위치를 변경시키고 반복을 종료한다.

이때, 청소기가 뒤로 이동하지 않도록 isClear 플레그를 true로 변경한다.

bool isClear = false;
for(int i = 0;i<4;i++){
      d--;
      if(d < 0)
         d = 3;
      int ny = r + dy[d];
      int nx = c + dx[d];
      if(ny < 0 || ny >= N || nx < 0 || nx >= M)
          continue;
            
      if(room[ny][nx] == 0){
         r = ny;
         c = nx;
         isClear = true;
         break;
      }
}

 

청소기가 뒤로 가는 방식도 d를 사용한다.

현재 위치에 d에 따라 dy, dx를 사용해 값을 감소시키면 뒤로 이동할 것이다.

if(!isClear){
   r -= dy[d];
   c -= dx[d];
}

 

이 문제는 구현이 주된 문제이기 때문에 어렵지 않게 해결할 수 있었다.

 

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

int N, M;
int room[51][51];
int r, c, d; // 0 : 북, 1 : 동, 2 : 남, 3 : 서
int dy[4] = {-1, 0, 1, 0}; // 북, 서, 남, 동
int dx[4] = {0, 1, 0, -1};
int answer = 0;

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

    cin>>N>>M; // 방 크기

    cin>>r>>c>>d; // 처음 좌표, 방향

    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++)
            cin>>room[i][j]; // 방 상태
    }

    while(room[r][c] != 1){
        if(room[r][c] == 0){
            room[r][c] = 2;
            answer++;
        }
        bool isClear = false;
        for(int i = 0;i<4;i++){
            d--;
            if(d < 0)
                d = 3;
            int ny = r + dy[d];
            int nx = c + dx[d];
            if(ny < 0 || ny >= N || nx < 0 || nx >= M)
                continue;
            
            if(room[ny][nx] == 0){
                r = ny;
                c = nx;
                isClear = true;
                break;
            }
        }
        if(!isClear){
            r -= dy[d];
            c -= dx[d];
        }
    }
    cout<<answer;
}