[백준] 14503번 로봇 청소기

문제

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

풀이

한시간 반동안 비슷하게 푼 거 같았지만 결국은 테스트케이스도 못맞췄다.

아직도 재귀호출을 구현하려면 머리가 아프다.

dx[4], dy[4] 에 북(0), 동(1), 남(2), 서(3) 순으로 저장을 했다.

현재 방향을 direction이라고 했을 때 북쪽을 보고 있는 경우를 제외하고 왼쪽 방향은 direction-1이기 때문에 이 점을 이용해 다음 방향을 정했다.

다음 칸이 청소해야되는 칸일 경우에 그 칸으로 이동한 후에 나머지 방향의 탐색은 하지 않는다.

다음 칸이 벽이거나 청소한 칸일 경우에는 방향만 바꿔주고 탐색을 계속 진행한다.

네 방향 모두 검사를 마친 후는 모두 청소한 칸이거나 벽인 경우이기 때문에 방향을 유치한 채로 후진을 해줬다.

후진에는 back_dx[4], back_dy[4] 를 따로 만들어 바라보는 방향에 따른 반대 방향을 저장해서 사용했다.

소스코드

#include <iostream>

using namespace std;

#define MAX_SIZE 51

// 바라보는 방향(북, 동, 남, 서)
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

// 바라보는 방향에 따른 후진 (남, 서, 북, 동)
int back_dx[4] = { 1,0,-1,0 };
int back_dy[4] = { 0,-1,0,1 };

int ans; // 로봇청소기가 청소하는 칸의 개수
int map[MAX_SIZE][MAX_SIZE];
int n, m; // 영역의 크기
int r, c, d; // 로봇청소기의 좌표(r,c), 바라보는 방향(d) : 북(0), 동(1), 남(2), 서(3)


void Dfs(int x, int y, int direction)
{
    // 벽이면 끝
    if (map[x][y] == 1) return;

    // 빈 칸이면 청소한다.
    if (map[x][y] == 0)
    {
        map[x][y] = 2;
        ans++;
    }

    // 네 방향 검사
    for (int k = 0; k < 4; k++)
    {
        // 북(0) -> 서(3), 동(1) -> 북(0), 남(2) -> 동(1), 서(3) -> 남(2)
        int next_direction = direction-1 < 0 ? 3 : direction-1;
        int next_x = x + dx[next_direction], next_y = y + dy[next_direction];

        // 빈 칸이면 청소
        if (map[next_x][next_y] == 0)
        {
            Dfs(next_x, next_y, next_direction);
            // 다음 칸으로 넘어간 경우에 더 이상 나머지 방향을 검사하지 않는다.
            return;
        }
        // 청소했거나 벽이면 방향만 바꿔준다.
        else
        {
            direction = next_direction;
        }
    }
    // 검사 끝

    // 네 방향 모두 청소했거나 벽이면 방향을 유지한채로 후진한다.
    int next_x = x + back_dx[direction], next_y = y + back_dy[direction];

    Dfs(next_x, next_y, direction);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    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];

    Dfs(r, c, d);

    cout << ans << "\n";

    return 0;
}