백준 14503 / 로봇 청소기

시뮬레이션 문제

문제에 나온 그대로 알고리즘을 구성하면 된다.

큐를 사용하되,

1번에서 2번작업으로 넘어가기전 4방향 탐색을 수행해 청소할 공간이 있는지 찾는다.

청소할 공간이 있다면 2-1로,

청소할 공간이 없다면 2-3으로 가되

2-3에서 청소기가 향하고 있는 방향 뒤쪽에 벽이 있다면 break;

없다면 후진을 한다.

부울 배열을 사용하여, 청소를 했으면 true 안되어있다면 false.

queue의 while문이 break 됬다면  

맵에서 true가 몇개 있는지 찾으면 그거시 정답.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
 
using namespace std;
 
int map[51][51];
bool check[51][51];
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int n, m,sx,sy,startdir;
 
    cin >> n >> m;    
    cin >> sx >> sy >> startdir;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    queue<tuple<int, int,int>>q;
 
    q.push({ sx,sy,startdir });
    check[sx][sy] = true;
 
    while (!q.empty()) {   // 0 북, 1 동, 2 남 ,3 서
        int x, y, dir;
        tie(x, y, dir) = q.front();
        q.pop();
 
        int nx, ny,ndir;
        int px, py;
 
        if (dir == 0) {
            nx = x;
            ny = y - 1;
            ndir = 3;
            px = x+1;
            py = y;
        }
        if (dir == 1) {
            nx = x - 1;
            ny = y;
            ndir = 0;
            px = x;
            py = y-1;
        }
        if (dir == 2) {
            nx = x;
            ny = y + 1;
            ndir = 1;
            px = x-1;
            py = y;
        }
        if (dir == 3) {
            nx = x + 1;
            ny = y;
            ndir = 2;
            px = x;
            py = y+1;
        }
 
        bool can = false;
 
        for (int i = 0; i < 4; i++) {
            int nnx = x + dx[i];
            int nny = y + dy[i];
 
            if (nnx >= 0 && nny >= 0 && nnx < n && nny < m) {
                if (map[nnx][nny] == 0 && check[nnx][nny] == false) {
                    can = true;
                    break;
                }
            }
        }
 
        if (can==true && nx >= 0 && ny >= 0 && nx < n && ny < m) {
            
            if (map[nx][ny] == 0 && check[nx][ny] == false) {
                check[nx][ny] = true;
                q.push({ nx,ny,ndir });
            }
            else {
                q.push({ x,y,ndir });
            }
        }
        if (can == false && nx >= 0 && ny >= 0 && nx < n && ny < m) {
 
            if (map[px][py] == 0) {
                q.push({ px,py,dir });
            }
            else {
                break;
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check[i][j] == true) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}