백준(BOJ) Implement 로봇 청소기 (14503) - GOLD5

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 $(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 $(N-1, M-1)$이다. 즉, 좌표 $(r, c)$는 북쪽에서 $(r+1)$번째에 있는 줄의 서쪽에서 $(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

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

입력

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 $N$개의 줄에 각 장소의 상태를 나타내는 $N \times M$개의 값이 한 줄에 $M$개씩 입력된다. $i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태를 나타내며, 이 값이 $0$인 경우 $(i, j)$가 청소되지 않은 빈 칸이고, $1$인 경우 $(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

문제 해결

골드 3~5 수준의 구현 문제이다. 이정도 난이도의 문제를 해결할 때는 그렇게 복잡한 알고리즘은 사용하지 않는다. 단지 주어진 조건에 맞게 코드를 구현할 수 있는 어느정도의 코드 구현력만 있으면 된다. 이번 문제에서의 핵심은 아무래도 반시계 방향으로 회전에 따른 방향 전환인것 같다. 일반화하기 어렵다면 그냥 해당 로직을 잘게 나눠서 해결하면 생각보다 어렵지 않게 해결할 수 있다. 나는 그냥 반시계 방향으로 회전하는 함수 1개와 회전 이후 move하는 함수1개 총 2개를 이용해서 회전 후 전진을 구현했다.

 

전체 코드

#include <iostream>
#include <vector>
#define MAX_SZ 50

using namespace std;

typedef long long ll;
typedef struct ROBOT{
    ll x;
    ll y;
    ll dir;
}ROBOT;

vector<vector<ll> >MAP(MAX_SZ, vector<ll>(MAX_SZ, 0));
ROBOT kobot;
ll CLEANEDROOM;
ll dx[4] = {0, 0, 1, -1};
ll dy[4] = {1, -1, 0, 0};

void init(ll n, ll m)
{
    cin >> kobot.y >> kobot.x >> kobot.dir;
    for(ll i=0; i<n; i++){
        for(ll j=0; j<m; j++){
            cin >> MAP[i][j];
        }
    }
    CLEANEDROOM = 0;
}

void clean_room(ll n, ll m){
    ll x = kobot.x; ll y = kobot.y; 
    if(MAP[y][x] == 0){ // 청소가 안되어 있다면
        MAP[y][x] = -1; // 청소 하고 갯수 증가
        CLEANEDROOM++;
    }
}

bool is_possible(ll x, ll y, ll n, ll m){
    if(x < 0 || x >= m)
        return false;
    if(y < 0 || y >= n)
        return false;
    return true;
}

bool find_room(ll n, ll m){
    bool evertyting_clean = true;
    ll x = kobot.x; ll y = kobot.y;
    for(ll i=0; i<4; i++){
        ll nx = x + dx[i];
        ll ny = y + dy[i];
        if(is_possible(nx, ny, n, m) == true && MAP[ny][nx] == 0){
            evertyting_clean = false;
            return evertyting_clean;
        }
    }
    return evertyting_clean;
}

bool move_back(ll n, ll m){ // 바라보는 방향을 유치한 채로 1칸 후진
    ll x = kobot.x ; ll y = kobot.y;

    if(kobot.dir == 0){ // 북
        y = y + 1;
    }
    else if(kobot.dir == 1){ // 동
        x = x -1;
    }
    else if(kobot.dir == 2){ // 남
        y = y -1;
    }
    else if(kobot.dir == 3){ // 서
        x = x + 1;
    }   
    if(is_possible(x ,y, n, m) == true && MAP[y][x] != 1){ // 이동이 가능하며 벽이 아닌 경우 후진
        kobot.x = x; kobot.y = y;
        return true;
    }
    return false;
}

void rotate(){
    if(kobot.dir == 0){ //  북 -> 서
        kobot.dir = 3; 
    }
    else if(kobot.dir == 1){ // 동 -> 북
        kobot.dir = 0;
    }
    else if(kobot.dir == 2){ // 남 -> 동
        kobot.dir = 1;
    }
    else if(kobot.dir == 3){ // 서-> 남
        kobot.dir = 2;
    }
}

bool move(){
    ll x = kobot.x; ll y = kobot.y;
    if(kobot.dir == 0){ //  북 
        y--;
    }
    else if(kobot.dir == 1){ // 동 
        x++;
    }
    else if(kobot.dir == 2){ // 남 
        y++;
    }
    else if(kobot.dir == 3){ // 서
        x--;
    }

    if(MAP[y][x] == 0){
        kobot.x = x; kobot.y = y;
        return true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);
    ll n =0; ll m =0;
    cin >> n >> m;
    init(n, m);
    // print(n, m);
    // ======================================================= init =================================================================

    while(1){
        // step 1 현재 칸이 청소가 되지 않았다면 청소
        clean_room(n, m);
        // step 2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우
        bool evertyting_clean = find_room(n, m); // 모두 청소가 되어있는 경우 true 반환

        if(evertyting_clean == true){ // 모두 청소가 되어 있으면 후진 가능성 확인
            bool possible_back = move_back(n, m);
            if(possible_back == true)
                continue; // 후진이 가능하면 방향을 유지한채 한 칸 후진 이후 step 1으로 
            if(possible_back == false){ //  후진이 불가능하다면 종료
                break;
            }  
        }
        // step 3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있는 경우,
        else{  
            for(ll i=0; i<4; i++){
                rotate(); // 청소되지 않은 공간 존재 하면 반시계 방향으로 90도 회전
                if (move() == true){ // 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
                    break;
                }
            }
        }
    }
    cout << CLEANEDROOM << "\n";

    return 0;
}