그래프/DFS

로봇 청소기

4gats 2023. 5. 23. 14:17

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

 

14503번: 로봇 청소기

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽

www.acmicpc.net

기본적인 구현 및 시뮬레이션 설정 후
DFS로 푸는 것이다!

방향을 돌리고
0이면 다시 dfs

청소할 구역이 없으면
뒤로 보내고 방향은 그대로 유지한 채
dfs
 

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
#include <iostream>
#include <cstring>
 
using namespace std;
 
int room[55][55];
int visited[55][55];
 
// 북, 동, 남, 서
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
int n, m;
int ans;
 
void dfs(int x, int y, int dir)
{
    for (int i = 0; i < 4; i++)
    {
        int next_d = (dir + 3 - i) % 4;
        int nx = x + dx[next_d];
        int ny = y + dy[next_d];
 
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || room[nx][ny] == 1)
        {
            continue;
        }
 
        if (room[nx][ny] == 0 && visited[nx][ny] == 0)
        {
            visited[nx][ny] = 1;
            ans++;
            dfs(nx, ny, next_d);
        }
    }
 
    int back_idx = dir > 1 ? dir - 2 : dir + 2;
    int back_x = x + dx[back_idx];
    int back_y = y + dy[back_idx];
 
    if (back_x >= 0 && back_x <  n && back_y >= 0 && back_y < m)
    {
        if (room[back_x][back_y] == 0)
        {
            dfs(back_x, back_y, dir);
        }
        else
        {
            cout << ans << '\n';
            exit(0);
        }
    }
}
 
int main()
{
    cin >> n >> m;
 
    int sx, sy;
    int input;
 
    cin >> sx >> sy >> input;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> room[i][j];
    }
 
    memset(visited, 0, sizeof(visited));
 
    ans++;
    visited[sx][sy] = 1;
    dfs(sx, sy, input);
}
 cs