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

[문제]

14503번: 로봇 청소기 (acmicpc.net)

14503번: 로봇 청소기

[문제 풀이]

방향을 고려하면서 청소기를 계속 이동시키는 시뮬레이션 문제이다.

보통 일반적으로 int dx[4] = {0,1,0,-1} 같이 쓰는 배열에서 방향이 중요한 문제.

 

//북 동 남 서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

 

이번 문제에서는 이와 같이 두고 풀었다. dx는 y축 dy는 x축의 위치를 좌우하는 배열으로 헷갈린다면 dx와 dy 배열의 이름을 바꾸면 된다.

북쪽으로 갈때는 y축으로 -1만큼 이동 동쪽으로는 x축을 +1만큼 이동 하는 방식으로 진행을 하였다.

 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
    a.바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
    b.바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3.현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
    a.반시계 방향으로 90도 회전한다.
    b.바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
    c.1번으로 돌아간다.

 

문제의 조건인데 여기서 주의사항은 3번의 a번이다.

근처에 빈 칸이 있으면 가던길 그대로 직진을 하는 것이 아니라 우선 회전을 한번 해야 한다는 점에 주의하도록 하자.

 

2번에서 후진을 하는 경우에는

dict = (dict + 2) % 4;

를 이용하면 0번 인덱스는 2번으로 1번과 3번은 서로 오갈수 있어서 방향이 정반대로 바뀐다.

 

또한 반시계 방향으로 회전하는 경우에는

dict = (dict - 1 + 4) % 4;

 

를 이용해서 방향을 바꾸었다. 반대로 시계방향의 경우에는 dict = (dict + 1) % 4 로 풀면 된다.

 

[회고]

시뮬레이션 문제는 아직 익숙하지 않아서 그런지 푸는데 상당히 오랜 시간이 걸린다.

풀다가 지치는 것이 시뮬레이션 문제를 틀리게 하는 가장 큰 문제 중 하나인듯. 집요하게 풀면 맞출 수 있으니 끈기있게 풀자!

 

[코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n,m;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
vector<vector<int> > arr;
vector<vector<int> > visited;

bool isRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < m){
        return true;
    }
    return false;
}

bool nearBlank(int x, int y){
    for(int i = 0; i<4;i++){
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if(isRange(nextX,nextY) == true){
            if(arr[nextX][nextY] == 0 && visited[nextX][nextY] == 0){
                return true;
            }
        }
    }
    return false;
}

int simu(int x, int y, int dict){
    int answer = 0;
    visited[x][y] = 1;
    answer++;

    while(true){
        //근처에 빈칸이 없다면
        if(nearBlank(x,y) == false){
            //뒤가 벽이 아니라면 후진, 벽이라면 종료.
            dict = (dict + 2) % 4;
            int nextX = x + dx[dict];
            int nextY = y + dy[dict];
            //범위 바깥이거나 벽이라면
            if(isRange(nextX,nextY) == false || arr[nextX][nextY] == 1){
                //종료.
                return answer;
            }
            //그렇지 않다면 후진.
            x = nextX;
            y = nextY;
            //방향은 유지한채 후진이니 다시 방향을 원상복귀 해주자.
            dict = (dict + 2) % 4;
        }
        //근처에 빈칸이 있다면
        else {
            for(int i = 0;i<4;i++){
                //+1은 시계방향.
                //-1 + 4는 시계 반대방향
                dict = (dict - 1 + 4) % 4;
                int nextX = x + dx[dict];
                int nextY = y + dy[dict];
                //다음칸이 범위 바깥이거나 공백이 아니거나 방문을 이미 했다면
                if(isRange(nextX,nextY) == false || arr[nextX][nextY] == 1 || visited[nextX][nextY] == 1){
                    //반시계 방향으로 가야한다. 북 -> 서 -> 남 -> 동
                    continue;
                }
                else {
                    x = nextX;
                    y = nextY;
                    break;
                }
            }
            visited[x][y] = 1; 
            answer++;
        }
    }

    return answer;
}

int main(){
    cin>>n>>m;
    arr.resize(n,vector<int>(m,0));
    visited.resize(n,vector<int>(m,0));

    int r,c,d;
    cin>>r>>c>>d;

    //시뮬레이션 문제.
    
    for(int i = 0;i<n;i++){
        for(int j = 0; j<m;j++){
            cin>>arr[i][j];
        }
    }

    cout<<simu(r,c,d)<<endl;


    return 0;
}