백준 알고리즘 14503

 

입력 : 장소의 크기 N*M, 초기 로봇청소기의 위치와 방향, 청소할 장소의 모양

출력 : 로봇청소기가 청소한 구역의 갯수

 

풀이

1. 로봇청소기가 특정 방향으로 움직일 때, 고려해야 할 상황은 총 3가지이다
    -> 이동할 곳이 벽인가
    -> 이동할 곳이 이미 청소를 한 곳인가
    -> 해당 방향으로 이동하면 범위를 벗어나는가

2. 세 가지를 모두 한번에 확인할 수 있도록 하기 위해 boolean타입의 테이블을 만들어 벽과 청소한 구역을 표시

3. N*M의 장소를 (N+1)*(M+1)로 바꿔 가장자리를 모두 벽으로 매꿔 한번에 세 가지 상황을 모두 고려하도록 함

4. 2번과 3번의 처리 이후엔 문제에 나온, 로봇청소기를 4가지 이동방식에 따라 r,c를 계산해 결과값을 출력한다.

 

소스코드

#include <iostream>
#include <string.h>
using namespace std;
 
int board[52][52];
bool cleaned[52][52];
 
int main() {
    int N, M;
    int r, c, d;
    int direction[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
    int cleanedRoom = 0;
    
    cin>>N>>M;
    cin>>r>>c>>d;
    
    for(int i=0; i<52; i++)
        for(int j=0; j<52; j++)
            board[i][j] = 1;
            
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) {
            cin>>board[i][j];
    
            if(board[i][j] == 0)
                cleaned[i][j] = true;
            else
                cleaned[i][j] = false;
        }
    }
    
    r++;
    c++;
    
    cleaned[r][c] = false;
    cleanedRoom++;
 
    while(true) {
        bool checkDirection = false;
        int nextD;
        int nextR;
        int nextC;
            
        for(int i=3; i>=0; i--) { 
            nextD = (i + d) % 4;
            nextR = r + direction[nextD][0];
            nextC = c + direction[nextD][1];
 
            if(!cleaned[nextR][nextC]){
                checkDirection = false;
                continue;
            }
            else{
                checkDirection = true;
                break;
            }
        }
 
        if(checkDirection){
            d = nextD;
            r = nextR;
            c = nextC;
            
            cleaned[r][c] = false;
            cleanedRoom++;
        }
        else if(board[r + direction[(2+d)%4][0]][c + direction[(2+d)%4][1]] == 1)
            break;
        else {
            r = r + direction[(2+d)%4][0];
            c = c + direction[(2+d)%4][1];
        }
    }
    
    cout<<cleanedRoom<<endl;
    
    return 0;
}