14503번_로봇 청소기_BOJ

문제 링크

14503번 주사위 굴리기 : https://www.acmicpc.net/problem/14503

문제 설명 및 해결 아이디어

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 출력하는 문제이다. 

현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 한다.

A. 현재 위치를 청소한다.

B. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.

a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한칸을 전진하고 A번부터 진행한다.

b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 B번으로 돌아간다.

c-1. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 B번으로 돌아간다.

c-2. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

이 문제는 네 방향 탐색을 이용하여 푼다.

주어진 문제에서 장소의 모든 외곽은 1로 주어지는 벽이라 했으므로, 따로 밖으로 벗어날 경우가 없으므로 탐색범위 체크를 해줄 필요가 없다.

방향은 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽이다.

바라보는 방향에서 왼쪽방향으로 회전할 것이므로, 다음과 같이 설정했다.

int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };

네 방향 모두 청소가 이미 되어있거나 벽인 경우(i==4), 한칸 후진을 하고, B번으로 돌아가야한다.

만약 뒤쪽 방향도 벽이라서 후진을 할 수 없을 경우 while루프를 빠져나와 프로그램을 종료하게한다.

코드

#include <cstdio>
using namespace std;
#define MAX_S 55
 
int n, m, px, py, d, sweep;
int map[MAX_S][MAX_S];
 
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
 
int main() {
    scanf("%d %d", &n, &m);
    scanf("%d %d %d", &px, &py, &d);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            scanf("%d", &map[i][j]);
    }
 
    bool f = 1;
    while (f) {
        if (!map[px][py])
            sweep++;
        map[px][py] = 2;
 
        for (int i = 0; i < 5; ++i) {
            if (i == 4) {
                int nx = px + dx[(d + 3) % 4];
                int ny = py + dy[(d + 3) % 4];
 
                if (map[nx][ny] != 1) {
                    px = nx;
                    py = ny;
                }
                else
                    f = 0;
 
                break;
            }
            int nx = px + dx[d];
            int ny = py + dy[d];
            d = (d + 3) % 4;
            if (!map[nx][ny]) {
                px = nx;
                py = ny;
                break;
            }
        }
    }
    printf("%d\n", sweep);
    return 0;
}