[구현] 로봇 청소기(14503)(C++)

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

14503번: 로봇 청소기

 

1. 문제 개요

 

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

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r, c)로 나타낼 수 있다.

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

1. 현재 위치를 청소한다.
2. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다.
   1. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다.
   2. 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면 한 칸 후진한다.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

로봇이 행동하는 역할을 while문 안에서 순서대로 구현할 수 있게끔했다.

또한 북, 동, 남, 서를 바라보고 있을 때 d의 값이 각각 0, 1, 2, 3이므로 방향이 d일때 앞으로 이동해야하는 좌표 값을 list에 pair로 저장해놓았다.

pair<int,int> dir[4] = {{-1,0},{0,1},{1,0},{0,-1}};

따라서 방향이 d일 때 앞으로 한 칸 이동하는 것은 다음과 같고,

r += dir[d].first;
c += dir[d].second;

뒤로 한 칸 이동하는 것은 다음과 같다.

r -= dir[d].first;
c -= dir[d].second;

또, 왼쪽으로 한 칸 이동하는 것은 방향이 북일때는 서쪽으로 한 칸 이동하는 것과 같으므로 다음과 같다.

d = (d+3)%4;
r += dir[d].first;
c += dir[d].second;

 

 

4. 전체 코드

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
pair<int,int> dir[4] = {{-1,0},{0,1},{1,0},{0,-1}};

int main(void) {
    int N, M, r, c, d;
    int place[51][51];
    scanf("%d%d%d%d%d",&N,&M,&r,&c,&d);
    
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            scanf("%d",&place[i][j]);
   
    int iter=0, sum=0;
    while(1) {
        if(place[r][c]==0){ // 현재 위치 청소
            place[r][c] = 2;
            sum++;
            iter = 0;
        }
        if(place[r+dir[(d+3)%4].first][c+dir[(d+3)%4].second]==0) {
        // 현재 위치 왼쪽에 청소할 공간이 있다면 그쪽으로 이동
            d = (d+3)%4;
            r += dir[d].first;
            c += dir[d].second;
        } else if(iter<4){
        // 그게 아니고 네 번 돌지 않았다면 왼쪽으로 회전
            d = (d+3)%4;
            iter++;
        } else {
        // 왼쪽에 청서 공간이 없고 네 번 돌았다면
            if(place[r-dir[d].first][c-dir[d].second]==1) // 뒤쪽이 벽이라면 작동 중지
                break;
            else { // 벽이 아니라면 한 칸 후진 
                iter = 0;
                r -= dir[d].first;
                c -= dir[d].second;
            }
        }
    }
    printf("%d",sum);
}