백준 15683 감시

작성일 | In |

Problem : 감시

유형 : DFS, 구현

문제, 예제 입출력 설명

설명하기에 너무 길어서 링크로 대체합니다

해결 전략

cctv가 있는 위치를 스택에 보관 한다.
cctv가 감시하고 있는 부분을, 해당 cctv가 감시하고 있다고 표시해둔다.
만약 모든 cctv를 확인했다면, 전체 사각지대에서 현재까지 감시한 장소를 빼서 비교해본다.

구현에서 팁이 있다면

  • cctv별로 관찰이 가능한 경우의 개수를 table로 만들어서 관리하면 시간을 줄일 수 있다.
  • cctv는 통과가 가능하므로
    • 사각지대 위치마다 감시하고 있는 cctv를 기록 해두면,
    • 다른 cctv에서 탐색시 사각지대 인곳만 확인하면 된다.

주의할 점

  • cctv 가 있는곳도 감시 하고 있는곳이다.

풀이

초기 정보를 입력받는다.

  • cctv의 위치를 스택에 넣어둔다.

  • 사각지대의 개수를 세본다.

  • int dir_size[] = { -1,4,2,4,4,1 };
    • 각 cctv별로 관찰가능한 경우의 개수를 dir_size 에 만들어 둔다.

Dfs를 한다.

  • 스택이 비어있다면, 모든 cctv를 접근해본 것이다.
    • 전체 사각지대 - 감시 하고 있는 사각지대 로 답과 비교해본다.
  • 새로운 board 를 만들어 사용할 것이므로, 기존 board를 save_board 에 백업해둔다.
  • 해당 cctv가 몇번 유형의 cctv인지 확인한다.
    • cctv 유형에 맞춰서, watch를 통해 구역을 확인한다.

감시 구역을 확인한다.

  • 보고 있는 방향으로, 중간에 벽 6 이 등장하기 전까지 탐색한다.
    • 해당 구역를 다른 cctv가 감시를 하고 있다면, 그냥 넘어간다. 겹치는 부분
    • 사각지대라면, 해당 위치에 현재 cctv의 유형이 감시하고 있다고 표시한다.
      • 감시하고 있는 사각지대의 개수를 증가시킨다.

코드

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define pp pair<int, int>
#define x first
#define y second

using namespace std;

int board[9][9];
int n, m;
int answer = INT_MAX;
int MAX_blind;

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

int dir_size[] = { -1,4,2,4,4,1 };
stack<pp> cctv;

int watch(int cur_x, int cur_y, int dir_x, int dir_y) {
    int nx = cur_x;
    int ny = cur_y;
    int cnt = 0;

    while (1) {
        nx += dir_x;
        ny += dir_y;

        if (nx < 0 or nx >= n or ny < 0 or ny >= m)return cnt;
        if (board[nx][ny] == 6)return cnt;

        if (board[nx][ny])continue;
        board[nx][ny] = board[cur_x][cur_y];
        cnt++;
    }
}

void dfs(int search_cnt) {
    if (cctv.empty()) {
        answer = min(answer, MAX_blind - search_cnt);
        return;
    }

    pp cur = cctv.top(); cctv.pop();
    int cctv_kind = board[cur.x][cur.y];

    int save_board[9][9] = { 0 };
    memcpy(save_board, board, sizeof(board));
    
    int dir_max = dir_size[cctv_kind];

    for (int dir = 0; dir < dir_max; ++dir) {
        int cnt = 0;
        int dir_x;
        int dir_y;

        if (cctv_kind == 2) {
            for (int i = 0; i <= 2; i += 2) {
                dir_x = dx[(dir + i) % 4];
                dir_y = dy[(dir + i) % 4];
                cnt += watch(cur.x, cur.y, dir_x, dir_y);
            }
        }

        else {
            int k = cctv_kind - 2;
            if (cctv_kind == 1) k = 0;

            for (int i = 0; i <= k; i++) {
                dir_x = dx[(dir + i) % 4];
                dir_y = dy[(dir + i) % 4];
                cnt += watch(cur.x, cur.y, dir_x, dir_y);
            }
        }

        dfs(search_cnt + cnt);
        memcpy(board, save_board, sizeof(board));
	}

    cctv.push({ cur.x,cur.y });
}

void solve() {
    dfs(0);
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            cin >> board[i][ii];
            if (board[i][ii] == 0) {
                MAX_blind++;
                continue;
            }
            if (board[i][ii] == 6)continue;
            cctv.push({ i,ii });
        }
    }
}

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

    input();
    solve();

    cout << answer;
    return 0;
}

피드백

양방향 이상의 경우, 2개 이상의 방향을 어떻게 탐색할까에 대해서 고민을 했다.
그냥 방향의 개수만큼 반복문을 돌리면 되는 부분 이었다.

스택이 비지 않았으면 해당 위치에서 가능한 경우의 수만큼 탐색할 뿐이다.
dfs 함수가 끝날때, 스택의 상태여부는 고려할 필요가 없다. 구현하다가 여기서 설계부분이 얽혀서 시간을 소모했다.

감시한 구역의 수를 세지않고, 마지막에 0인 구역만 세보는 방식과 속도가 똑같다. 4ms
코드
0ms는 어떻게 나오는 걸까 궁금하다.