백준 14503 로봇 청소기

작성일 | In |

Problem : 로봇 청소기

유형 : DFS, 구현

문제 설명

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

  • 현재 위치를 청소한다.
  • 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
    • 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
    • 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    • 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    • 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

예제 입력

1
2
3
4
5
6
7
8
9
10
11
12
13
11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력

1
57

해결 전략

시키는대로 구현하면 된다.
움직이는 방향은 시계 반대 방향이다.
벽이 주위를 다 막고 있기 때문에 범위 벗어나는건 따로 체크해주지 않아도된다.

주의할 점

  • 직진하거나 후진한 다음에, 보고 있는 방향이 아니라 바로 왼쪽으로 돌아서 체크한다.
  • 로봇이 시작한 위치는 청소를 한것이므로, 답의 최소값은 1이다.

풀이

4방향으로 돌려본다.

  • 청소가 가능하다면, 그쪽으로 가서 청소한다.
  • 청소가 불가능하다면 후진한다.

그냥 문제에서 시키는대로 하면된다…

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define MAX 51

using namespace std;

int board[MAX][MAX];
bool visit[MAX][MAX];

int n, m;

int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int answer = 1;
bool finished;

void dfs(int x, int y, int cmd);

void back_move(int x, int y, int cmd) {

    int dir = (cmd + 2) % 4;
    int nx = x + dx[dir];
    int ny = y + dy[dir];

    if (board[nx][ny]) {
        cout << answer << "\n";
        finished = true;
        return;
    }
    dfs(nx, ny, cmd);
}


void dfs(int x, int y , int cmd) {
    if (finished)return;

    bool can_clean = false;
    int dir;

    for (int i = 1; i <= 4; ++i) {
        dir = cmd - i;
        if (dir < 0) dir += 4;
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (board[nx][ny])continue;
        if (visit[nx][ny])continue;
        
        visit[nx][ny] = true;
        can_clean = true;
        answer++;
        dfs(nx, ny, dir);
        break;
    }

    if (!can_clean) {
        back_move(x, y ,cmd);
    }
}

void input() {
    cin >> n >> m;
    int start_x, start_y, cmd;
    cin >> start_x >> start_y >> cmd;

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            cin >> board[i][ii];
        }
    }

    visit[start_x][start_y] = true;
    dfs(start_x, start_y, cmd);
}

int main()
{
    ios_base::sync_with_stdio(false);
    freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    input();
    return 0;
}

피드백

x, y 로 좌표 적는거 실수 안하게 조심하자.