[BaekJoon/백준] 14503번 로봇 청소기

 

문제에 제시되어 있는 대로 진행하는데, 헷갈릴 만한 점과 주의할 점이 있다.

 

 

문제 정의

1. 우선 로봇청소기는 현재 위치를 청소한다.

 

2 - 1. 현재 바라보는 방향에서 왼쪽 방향의 한 칸이 아직 청소되지 않았다면, 왼쪽 방향으로 회전한 뒤에 한 칸 이동하고 1로 돌아간다.

 

2 - 2. 현재 바라보는 방향에서 왼쪽 방향의 한 칸이 벽이거나, 이미 청소되었다면, 왼쪽 방향으로 회전만 한다.

 

3. 2 - 2가 연속 4번 진행된 경우, 현재 바라보는 방향에서 뒷쪽 방향으로 후진할 수 있다면(벽이 아니다 = 이미 청소되었다) 후진하고, 후진할 수 없다면 종료한다.

 

 

주의할 점

 A. 청소할 땐(2-1) 방향 전환 후 직진. 네번 돌고 뒤가 벽이 아니면(3) 방향은 그대로인데 후진.

 B. 연속 네번이라는 점이 중요함. 따라서 회전하여 청소를 해줬을 경우에 카운트를 초기화시켜줘야함.

 

#include <iostream>

using namespace std;



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

// (x + 3) % 4 하면 왼쪽 회전이겠다.

int N, M;
int Arr[51][51];

int Rx, Ry, Rd;
int ea_count; // 제자리 회전 횟수 카운트
int clean_count; // 청소 갯수

void dfs(int x, int y) {
    
    
    
    int D = (Rd + 3) % 4; // 현재에서 왼쪽방향
    
    int tx = x + mx[D];
    int ty = y + my[D];
    
    if(Arr[tx][ty] == 0) { // 왼쪽으로 돌았는데, 청소할 수 있다면 청소
        
        ea_count = 0; // 연속 네번이라는 것이 중요함. 따라서 청소했으면 초기화.
        
        // 방향 전환
        Rd = D;
        
        // 위치 이동
        Rx = tx;
        Ry = ty;
        
        // 이동한 위치 청소
        Arr[Rx][Ry] = 2;
        clean_count++;
        
        dfs(tx, ty);
                

    } else { // 왼쪽으로 돌았는데, 벽이거나 이미 청소한 위치라면
        
        
        if(ea_count == 4) { // 네번 제자리 회전 한 경우
            
            ea_count = 0; // 초기화.
            
            
            int D = (Rd + 2) % 4;
            
            int tx = x + mx[D];
            int ty = y + my[D];

            
            if(Arr[tx][ty] == 1) // 뒤쪽이 벽이라면
                return; // 작동 멈춤.
            
            else { // 뒤쪽이 벽이 아니라면 ( = 이론 상, 청소한 위치(2)일 수 밖에 없음)
                
                // 위치 이동 ( = 후진)
                Rx = tx;
                Ry = ty;
                                
                dfs(tx, ty);
                        

            }
        } else { // 아직 4번까지는 회전 안한 경우
            
            ea_count++;
            Rd = D;
            dfs(x, y); // 다시 시작.
        }
        
        
        
    }
    
    
}

int main() {
    
    
    cin >> N >> M;
    
    cin >> Rx >> Ry >> Rd;
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < M; j++) {
            
            cin >> Arr[i][j];
        }
    }
    
    
    
    Arr[Rx][Ry] = 2; // 일단 현재 위치 청소
    clean_count++;
    
    
    dfs(Rx, Ry);
    
    
    cout << clean_count << "\n";
}

 

 

소요 시간 : 50분