[Algorithm] 백준 14503번 로봇 청소기

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

 

문제 풀이

복잡한 설명이지만 굉장히 간단하게 생각해야한다.

 

후진의 경우도 방향을 그대로 살려서 각 방향에 따라 진행하는 방향의 반대로 가기 때문에

현재 좌표에서 빼줌으로써 해결하면 좋음 :)

 

문제에서 유일하게(?) 조심해야할 점은 일반적으로 "동,서,남,북" 이라고 말하고 쓰는데, 

"북, 동, 남, 서"를 기준으로 문제를 해석해나가야함 !

 

시뮬레이션 부분에서 예전보다 많이 어려움을 느끼는 것 같다. 

#pragma warning(disable: 4996)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {};
    Point(int x, int y) : x(x), y(y) {};
};
 
int N, M;
int robotX, robotY, robotDir;
int map[51][51];
int answer = 0;
 
int dx[4] = { -1, 0, 1, 0};
int dy[4] = { 0,1, 0, -1 };
 
void dfs(int x, int y, int dir) {
    if (map[x][y] == 1) return;
    if (map[x][y] == 0) {
        map[x][y] = 2;
        answer++;
    }
    int nextDir, nextX, nextY;
    for (int i = 0; i < 4; i++) {
        nextDir = dir - 1 < 0 ? 3 : dir - 1;
        nextX = x + dx[nextDir];
        nextY = y + dy[nextDir];
 
        if (map[nextX][nextY] == 0) {
            dfs(nextX, nextY, nextDir);
            return;
        }
        else {
            dir = nextDir;
        }
    }
    dfs(x - dx[dir], y - dy[dir], dir);
}
int main()
{
    // 0 북쪽 1 동쪽 2 남쪽 3 서쪽
    scanf("%d %d", &N, &M);
    scanf("%d %d %d", &robotX, &robotY, &robotDir);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    dfs(robotX, robotY, robotDir);
    printf("%d", answer);
    return 0;
}