로봇 청소기

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 07:44 ~ 09:37
int dx[4] = {0, 1, 0, -1}; // 북, 동, 남, 서 (dir감소 -> 왼쪽 회전)
int dy[4] = {-1, 0, 1, 0};
int N, M, ans=1, D;
int y, x;
int board[52][52];
bool vis[52][52];
void left(){
    D--;
    if(D<0) D+=4;
}
int reverse(){
    int newD = D;
    newD +=2;
    if(newD>3) newD -=4;
    return newD;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    cin >> y >> x >> D;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> board[i][j];
    vis[y][x] = true;
    board[y][x] = 2;
    int reverseCnt = 0;
    while(true)
    {
        int tD = D-1;
        if(tD<0) tD+=4;
        int ny = y + dy[tD]; // 실제 검사는 왼쪽을 하기 때문에 D-1이 필요
        int nx = x + dx[tD];
        /* 방향전환을 4번해서 후진해야 하는 경우 */
        if(reverseCnt == 4){
            int nD = reverse();
            int nny = y + dy[nD];
            int nnx = x + dx[nD];
            if(board[nny][nnx] == 1) goto stop;
            if(!vis[nny][nnx]){
                vis[nny][nnx] = true;
                board[nny][nnx] = ++ans;
                reverseCnt = 0;
            }
            y = nny;
            x = nnx;
            reverseCnt = 0;
            continue;
        }
        /* 벽이면 방향 전환 */
        if(board[ny][nx] == 1 or vis[ny][nx] == true){
            left();
            reverseCnt++;
            continue;
        }
        /* 이동해서 청소할 수 있는 경우 */
        vis[ny][nx] = true;
        board[ny][nx] = ++ans;
        reverseCnt = 0;
        left();
        y = ny;
        x = nx;
    }
    stop:;
    cout << ans;
    return 0;
}

• 로직
  • 현재 방향(북, 동, 남, 서)에 맞춰 dx[] / dy[] 설정
  • 현재 방향을 기준으로 왼쪽 방향을 임시 방향 tD로 두고 검사할 좌표를 표시 (ny, nx)
  • 벽이라면 dir을 감소시켜서 왼쪽으로 전환 / 동시에 후진을 위한 reverseCnt++
  • reverseCnt가 4라면 후진 한번 한 뒤 다시 4방향을 검사
  • 후진을 할 수 없는 상황이라면 종료

• 문제 이해
  • 청소한 자리로 후진할 수 없다고 이해해서 문제 풀이가 오래 걸림
    --> 벽일 경우에만 종료이고, 청소한 자리라면 후진하여 4방향을 다시 검사할 수 있음
  • Test Case 2번의 움직임은 다음과 같다

• 느낀 점
  : 시뮬레이션 문제는 문제에 대한 이해가 어려운 경우가 있어서 확실히 하고 넘어가야 할 듯