[C++] 백준 BOJ 14503 로봇 청소기

문제링크 : https://boj.kr

시뮬레이션 문제로 주어진 조건에 맞게 그대로 풀어내려가면 되는 문제이다.

문제 접근 방법은 DFS 방식이랑 크게 차이 없지만 DFS로 풀면 스택이 계속 쌓이기 때문에 이렇게 푸는 편이 더 좋지 않을까 생각한다.

// BOJ 14503 로봇 청소기
#include <iostream>
#include <vector>
 
using namespace std;
 
struct pt{
    int x, y, d;
};
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
 
void turn(int& dir){
    dir = --dir < 0 ? 3 : dir; // 왼쪽 회전
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int N, M;
    int x, y;
    int nx, ny;
    int dir; // 0-북 1-동 2-남 3-서
    int ans = 0;
    cin >> N >> M >> x >> y >> dir;
    x++, y++; // 계산 편의상 1씩 더함
    vector<vector<int> > map(N + 2, vector<int>(M + 2, 1));
    for(int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> map[i][j];
 
    while(true){
        // 현재 위치를 청소한다.
        if(map[x][y] == 0){
            map[x][y] = 2;
            ans++;
        }
        bool chk = false;
        // 현재 위치에서 현재 방향을 기준으로
        // 왼쪽방향부터 차례대로 탐색을 진행한다.
        for(int i = 0; i < 4; i++) {
            turn(dir);
            nx = x + dx[dir];
            ny = y + dy[dir];
            // 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면,
            if (map[nx][ny] == 0) {
                // 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
                chk = true; // 1번으로 가기 위한 플래그 변수
                x = nx;
                y = ny;
                break;
            }
        }
        if(chk) // 1번 ㄱㄱ
            continue;
        // 반대방향
        nx = x - dx[dir];
        ny = y - dy[dir];
        // 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는,
        // 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
        if(map[nx][ny] != 1){
            x = nx;
            y = ny;
            continue;
        }
        // 네 방향 모두 청소가 이미 되어있거나 벽이면서,
        // 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
        else
            break;
    }
    cout << ans;
 
    return 0;
}