[삼성 기출 문제] 백준 14503 로봇 청소기

문제 링크 

클릭시 문제로 이동합니다!

어떻게 풀까?

전형적인 시뮬레이션 문제입니다!

문제에서 요구하는 것들을 잘 분석해서 순서에 유의해서 잘 구현하면 됩니다!!

이 문제에서 조금 생각해봐야할 부분은 로봇 청소기가 청소를 종료해야하는 상태와 후진해야하는 상태를 구분해야한다는 것입니다.

그래서 저는 상태를 다음과같은 3가지 상태로 표현했습니다.

-1: 청소를 종료해야함

- 4 방향 모두 청소가 되어있는데, 뒤가 이동 불가능한 지역

1 : 청소기가 이동함.

- 4 방향 중 청소가 안된 방향으로 이동

- 4 방향 모두 청소가 되어있어서 현재 바라보는 방향에서 뒤 칸으로 이동

2 : 청소가 이미 되어있어서 청소가 안된 곳 발견 필요

상태가 -1이 나오면, 함수에서 return값으로 현재까지 청소한 구역의 개수를 반환합니다.

상태가 1이 나오면, 청소기가 이동하고, 이동한 자리가 청소가 안된 지역이라면 청소한 구역의 수를 1 늘려줍니다!

상태가 2가 나오면 청소기의 방향만 반시계 방향으로 회전한 뒤에 다시 청소 구역을 찾아봅니다.

아래 그림을 통해서 확인해 보겠습니다.

첫번째 경우엔, 바라보는 방향 왼쪽 방향이 청소가 안된 구역이기 때문에 청소기가 해당 방향을 바라보면서 한칸 이동합니다. 그리고 해당 위치를 청소하고, 청소된 지역을 하나 늘려줍니다.

두번째 경우엔, 바라보는 방향 왼쪽 방향이 청소가 이미 되어있기 때문에, 청소기를 회전만 하고 2를 return하여 계속해서 함수를 진행합니다.

세번째 경우엔, 네 방향이 모두 청소가 되어있고, 뒤로 후진할 수 있기 때문에 로봇청소기를 후진한 뒤에 청소기가 이동했다는 표시의 1을 반환합니다.

마지막 경우에는, 네 방향 모두 청소가 되어있거나 벽이지만, 뒤에가 벽이기 때문에 -1을 반환하고, 청소를 종료합니다.

현재까지 청소된 구역의 개수를 반환합니다.

코드

#include<iostream>
#include<cstring>
#include<cstdio>
 
using namespace std;
 
int map[50][50];
const int dr[4] = {-1,1,0,0};
 
    int n ,m;
const int dc[4] = {0,0,-1,1};
const int change[4][4] = {{2,1,3,0},{0,2,1,3},{3,0,2,1},{1,3,0,1}};
const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
struct Cleaner
{
    int direct;
    int r,c;
    int clean;
    int check()
    {
        int nextR = r + dr[change[direct][0]];
        int nextC = c + dc[change[direct][0]];
 
        bool dirty = false;
 
        for(int i = 0 ; i < 4; i++)
        {
            nextR = r + dr[i];
            nextC = c + dc[i];
 
            dirty |= map[nextR][nextC] == 0;
        }
 
        if(!dirty)
        {
            nextR = r + dr[change[direct][1]];
            nextC = c + dc[change[direct][1]];
            if(map[nextR][nextC] == 1) return -1;
            r = nextR; c = nextC;
            return 2;
        }
 
        nextR = r + dr[change[direct][0]];
        nextC = c + dc[change[direct][0]];
 
        if(map[nextR][nextC] == 0)
        {
            r = nextR;
            c = nextC;
            direct = (direct+3)%4;
            return 1;
        }
 
        direct = (direct+3)%4;
        return 2;
    }
   int process()
   {
       while(true)
       {
           if(map[r][c] == 0) 
           {
               map[r][c] = 2;
               clean++;
           }
 
 
           while(true)
           {
               int flag = check();
               if(flag == 1) break;
               if(flag == -1) return clean;
               
           }
       }
   }
} cleaner;
int main()
{
    scanf("%d %d\n", &n, &m);
    scanf("%d %d %d\n", &cleaner.r, &cleaner.c, &cleaner.direct);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0 ; j < m ; j++)
            scanf("%d",&map[i][j]);
    }
 
    int res = cleaner.process();
    printf("%d\n", res);
    return 0;
}

시간 복잡도

최악의 경우는 로봇 청소기가 모든 구역을 청소하는 경우이기 때문에 입니다.