백준 14503번: 로봇 청소기 (C++)

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

로봇의 위치와 방향을 관리하며 bfs를 돌려주면 된다. 모든 순간에 로봇은 하나이기 때문에 큐에는 최대 하나의 좌표(로봇의 좌표)만 들어갈 수 있다.

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
struct Robot {
    int r, c;
}bot;
int dir;
int row, col, m[51][51];
bool vis[51][51];
queue<Robot> q;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
int cnt = 1;
pii getBackPos(int r, int c, int dir) {
    if (dir == 0)
        return { r + 1, c };
    else if (dir == 1)
        return { r, c - 1 };
    else if (dir == 2)
        return { r - 1, c };
    else
        return { r, c + 1 };
}
void bfs(Robot bot) {
    q.push(bot);
    vis[bot.r][bot.c] = true; // 로봇 시작 위치 청소
    while (!q.empty()) {
        Robot cur = q.front();
        q.pop();
        //int doneCnt = 0;
        bool goBack = true;
        for (int i = 0; i < 4; i++) {
            dir = (dir + 3) % 4;
            int nr = cur.r + dr[dir];
            int nc = cur.c + dc[dir];
            if (nr < 0 || nc < 0 || nr >= row || nc >= col || vis[nr][nc] !=0 || m[nr][nc] != 0) {
                //doneCnt++;
                continue;
            }
 
            else {
                //printf("%d, %d 방향 %d에서 %d, %d 방향 %d로 이동\n", cur.r, cur.c, cur.dir, nr, nc, (cur.dir+3)%4);
                q.push({ nr, nc });
                vis[nr][nc] = true;
                cnt++;
                goBack = false;
                break;
            }
        }
        //if (doneCnt == 4) {
        if(goBack){
            //dir = (dir + 1) % 4;
            //printf("%d %d 방향 %d 상태에서 후진시도\n", cur.r, cur.c, cur.dir);
            pii tmp = getBackPos(cur.r, cur.c, dir);
            if (tmp.first < 0 || tmp.second < 0 || tmp.first >= row || tmp.second >= col
                 || m[tmp.first][tmp.second] == 1)
                return;
 
            //후진 가능한경우
            else {
                q.push({ tmp.first, tmp.second});
                
            }
    
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> row >> col;
    cin >> bot.r >> bot.c >> dir;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
    
    bfs(bot);
    
    cout << cnt;
    return 0;
}