[algorithm] 백준 - 로봇 청소기

이 문제는 시뮬레이션, bfs문제이다.

 

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

 

 우선 왼쪽 방향으로 전진하는 함수, 후진하는 함수를 따로 작성해뒀다.

 

int turnDirection(int pd){
    int direction;
    switch(pd){
        case 0:
        return 3;
        case 1:
        return 0;
        case 2:
        return 1;
        default:
        return 2;
    }
}

 

int backDirection(int pd){
    switch(pd){
        case 0:
        return 2;
        case 1:
        return 3;
        case 2:
        return 0;
        default:
        return 1;
    }
}

 

 

현 위치에서 4가지 방향에 대해 청소를 하지않은 공간을 탐색한다.

1이라면, 왼쪽 방향으로 회전 후, 앞으로 전진한 좌표를 queue에 삽입한다.

방향을 바꿨으므로 현 위치에서 4가지 방향을 살펴볼 이유가 없기 때문에 반복문을 탈출한다.

그리고 2인지 3인지를 확인할 필요가 없다는 boolean값을 설정한다.

 

tuple<int,int,int> node = q.front();
        q.pop();
        int direction = get<2>(node);
        for(int i = 0; i < 4; i++){
            direction = turnDirection(direction);
            int dx = directx[direction] + get<0>(node);
            int dy = directy[direction] + get<1>(node);
            if(dx < n && dx >= 0 && dy < m && dy >= 0 && vertex[dx][dy] == 0){
                answer++;
                vertex[dx][dy] = 2;
                isBlocked = false;
                q.push({dx,dy,direction});
                break;
            }
        }

 

그렇지만 4가지 방향에 대해 청소를 하지 않은 공간을 찾지 못했다면 뒤쪽 방향이 벽인지 확인 후 후진한다,

그리고 방향과 좌표를 queue에 삽입한다.

 

if(isBlocked){
            int direction = backDirection(get<2>(node));
            int dx = directx[direction] + get<0>(node);
            int dy = directy[direction] + get<1>(node);
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && vertex[dx][dy] != 1){
                q.push({dx,dy,get<2>(node)});
            }
        }

 

 

완성된 코드는 이렇다.

//로봇 청소기
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

int vertex[50][50];
int directx[] = {-1,0,1,0};
int directy[] = {0,1,0,-1};
int n,m;
int turnDirection(int pd){
    int direction;
    switch(pd){
        case 0:
        return 3;
        case 1:
        return 0;
        case 2:
        return 1;
        default:
        return 2;
    }
}
int backDirection(int pd){
    switch(pd){
        case 0:
        return 2;
        case 1:
        return 3;
        case 2:
        return 0;
        default:
        return 1;
    }
}
int bfs(int x, int y, int d){
    queue<tuple<int,int,int>> q;
    q.push({x,y,d});
    vertex[x][y] = 2;
    int answer = 1;
    while(!q.empty()){
        bool isBlocked = true;
        tuple<int,int,int> node = q.front();
        q.pop();
        int direction = get<2>(node);
        for(int i = 0; i < 4; i++){
            direction = turnDirection(direction);
            int dx = directx[direction] + get<0>(node);
            int dy = directy[direction] + get<1>(node);
            if(dx < n && dx >= 0 && dy < m && dy >= 0 && vertex[dx][dy] == 0){
                answer++;
                vertex[dx][dy] = 2;
                isBlocked = false;
                q.push({dx,dy,direction});
                break;
            }
        }
        if(isBlocked){
            int direction = backDirection(get<2>(node));
            int dx = directx[direction] + get<0>(node);
            int dy = directy[direction] + get<1>(node);
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && vertex[dx][dy] != 1){
                q.push({dx,dy,get<2>(node)});
            }
        }
    }
    return answer;
}
int main(void){
    cin >> n >> m;
    int x, y, d;
    cin >> x >> y >> d;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
           cin >> vertex[i][j];
        }
    }
    cout << bfs(x,y,d);
}