#14503. 로봇 청소기

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

1. 문제 이해

  

 삼성 기출 문제 입니다. 

 시뮬레이션 문제인데, 과정을 자세히 보면 dfs와는 다른것을 볼 수 있습니다.

처음에 이 문제를 dfs로 접근 하였다가 멘토님의 도움으로 while문으로 해결하는 문제라는것을 깨닳았습니다.

(그러니... 꼭 다시 풀어보자!!)

2. 접근 방법

 문제의 루틴대로 따라가면서 while문을 작성해 봅시다.

여기서 핵심은 flag!!

1) 4방향을 모두 탐색하였는데, 청소할곳(0)을 못찾은 경우에 루틴으로 가기 위한 flag!

2) 뒤로 가봤는데 뒤에가 벽인 경우는 탈출할수 있도록!!

3) 뒤로 가봤는데 뒤에가 벽이 아닌 경우는 방향을 그대로 가져 가도록 합시다!!

위에 3가지를 생각하면서 코딩에 들어가면 문제 끄~~~읏!!!

3. 문제 해결

#include <iostream>
#define MAX_SIZE 50
using namespace std;
 
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
int n, m;
int map[MAX_SIZE][MAX_SIZE];    // 1:벽, 2:청소
 
int next_dir(int d) {
    return (d + 1) % 4;
}
 
bool map_impossible(int x, int y) {
    if (x < 0 || y < 0 || x >= m || y >= n) return 1;
    return 0;
}
 
int main() {
 
    int r, c, d;
 
    cin >> n >> m;
    cin >> r >> c >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int x = c, y = r;
 
    if (d == 1) d = 3;
    else if (d == 3) d = 1;
 
    int res = 0;
    while (true) {
 
        if (map[y][x] == 0) {
            map[y][x] = 2;
            res++;
        }
 
        bool search_flag = false;
 
        for (int i = 0; i < 4; i++) {
            d = next_dir(d);
 
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (map_impossible(nx, ny) || map[ny][nx] != 0) continue;
 
            x = nx;
            y = ny;
            search_flag = true;
            break;
        }
 
        if (search_flag) continue;
 
        // 4방향 모두 못찾았을 때
 
        d = next_dir(d + 1);    // 뒷 방향
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if (map_impossible(nx, ny) || map[ny][nx] == 1) break;
 
        // 뒤가 벽이 아니면 
        d = next_dir(d + 1);    // 방향 유지한 채
        x = nx;                    // 뒤로 가기
        y = ny;
    }
 
    cout << res << '\n';
    return 0;
}