[BOJ-14503]로봇 청소기

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

[문제요약]

로봇 청소기(이하 로봇)가 주어 졌을 때 청소하는 영역의 개수를 구하는 프로그램 작성한다.

로봇이 있는 장소는 N * M 크기 직사각형으로 나타낸다. 1 * 1 크기의 정사각형 칸으로 나누어져 있다.

각각의 칸은 벽(1) 또는 빈칸(0) 이다.

로봇은 바라보는 방향이 존재한다. 방향은 북(0), 동(1), 남(2), 서(3) 중 하나이다.

아래 조건과 같이 작동한다.

1. 현재위치를 청소한다.
2. [조건 1] 현재위치가 청소되어 있다면, 현재 위치에서 현재 방향을 기준, 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재하면, 그 방향으로 회전한 후 한 칸 전진 후 [조건 1]을 진행한다.
   2. 왼쪽 방향에 청소할 위치가 없다면, 그 방향으로 회전 후 [조건 2-1]로 돌아간다.
   3. 4-방향이 모두 청소가 되어있거나 벽인 경우, 바라보는 방향을 유지한 채 한 칸 후진하고 [조건 2-1]로 돌아간다.
   4. 4-방향이 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우 작동을 멈춘다.

     로봇은 이미 청소되어있는 칸을 또 청소할 수 없고, 벽을 통과할 수 없다.

[입력]

세로(행) 크기 N, 가로(열) 크기 M 이 주어진다. N,M~[3, 50]

로봇이 있는 좌표와 방향이 주어진다.

로봇이 청소할 N*M의 정보가 주어진다.

[출력]

로봇이 청소하는 칸의 개수를 출력한다.

[접근방법]

주어진 조건을 구현하는 문제이다. 

문제 조건에 맞춰 코드를 작성하면 된다. 

소스코드에 각 조건을 어떻게 구현하였는지 주석으로 위치를 표시하였다.

[C++11 source 구현]

#include<cstdio>
#define din1(a) scanf("%d", &a)
#define din2(a,b) scanf("%d%d", &a, &b)
#define din3(a,b,c) scanf("%d%d%d", &a, &b, &c)
 
const int M = 55;
const int dir[] = { 0, 1, 2, 3 };
const int dr[] = { -1, 0, 1, 0};
const int dc[] = { 0, 1, 0, -1};
 
int imap[M][M];
int ROW, COL;
 
struct ROBOT {
    int R;
    int C;
    int D;
    ROBOT(): R(0), C(0), D(0) {}
    ROBOT(int ir, int ic, int id): R(ir), C(ic), D(id) {}
};
 
int main() {
    int ans = 0;
    // input
    din2(ROW, COL);
    int tmp[3];
    din3(tmp[0], tmp[1], tmp[2]);
    ROBOT rbt = ROBOT(tmp[0], tmp[1], tmp[2]);
    for (int r = 0; r < ROW; r++) {
        for (int c = 0; c < COL; c++) {
            din1(imap[r][c]);
        }
    } 
    // input end
 
    /* 
    청소X : 0
    청소O : 2
    벽     : 1
    */
 
    int rotate = 0;
 
    while (1) {
        int hr = rbt.R;
        int hc = rbt.C;
        int hd = rbt.D;
        int& here = imap[hr][hc];
        if (here == 0) {
            here = 2, ans++;
            continue;
        } // condition 1
 
        int sch_d = (hd - 1 < 0) ? 3 : hd - 1;
        int sch_r = hr + dr[sch_d];
        int sch_c = hc + dc[sch_d];
        int block = 0;
 
        for (int i = 0; i < 4; i++) {
            if (imap[hr + dr[i]][hc + dc[i]] == 1) block++;
        } // condition 2-4
        if (block == 4) break;
 
        if (0 <= sch_r && sch_r < ROW &&
            0 <= sch_c && sch_c < COL && (rotate != 4) ) {
            if (imap[sch_r][sch_c] == 0) {
                rbt.R = sch_r;
                rbt.C = sch_c;
                rbt.D = sch_d;
                rotate = 0;
            } // condition 2-1
            else{
                rbt.D = sch_d;
                rotate++;
            } // condition 2-2
            continue;
        }
 
        if (rotate == 4) {
            int bd = (rbt.D + 2) % 4;
            int br = hr + dr[bd];
            int bc = hc + dc[bd];
            if (imap[br][bc] != 1) rbt.R = br, rbt.C = bc; // condition 2-3
            else if (imap[br][bc] == 1) break; // condition 2-4
            rotate = 0;
        }
    }
 
    printf("%d", ans);
 
    return 0;
}