[C++] 백준 15683 - 감시

🔐 백준 15683 - 감시

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

🔑 풀이

사무실은 최대 $ 8 \times 8 $ 크기이며, CCTV의 개수 역시 8개 이하이다. 또한 CCTV의 유형이

5가지이며, 5번을 제외한 CCTV들은 회전이 가능하므로(정확히는 5번은 회전의 의미가 없음) 모든

경우의 수는 최대 $ 4^8 $ 이라고 생각했다.(4방향 회전이 가능한 CCTV 8개가 감시할 수 있는 경우의 수)

이 숫자는 대략 65000 정도이므로, 1초의 시간 제한에 충분하다고 생각했다.

또한, 이 문제를 그리디 알고리즘으로 접근하려고도 했었는데, 5번을 제외하고, 다른 CCTV의 방향을

결론지을 수 있는 근거를 찾지 못했다. 그러므로 모든 경우의 수를 전부 탐색하는 브루트 포스 방식으로

코드를 짜려고 했다.

watch 함수

CCTV의 방향이 정해졌을 때, 감시 영역은 벽을 만나거나, 배열의 끝에 도달했을 때까지 이어져야 한다.

빈 칸인 경우 감시 영역임을 표시해주어야 하므로, 숫자 7로 표시해 주었다.

void watch(vector<vector<int>>& v, int x, int y, int dir) {
    while (true) {
        x += dx[dir];
        y += dy[dir];

        if (x < 0 || x >= N || y < 0 || y >= M) return;
        if (v[x][y] == 6) return;
        if (v[x][y] == 0) v[x][y] = 7;
    }
}

dfs

CCTV의 정보를 저장하기 위해, 처음 사무실 각 칸의 정보를 입력받을 때, cctv 배열에

CCTV의 번호, x,y 좌표를 저장해주었고, 각각의 CCTV의 방향을 저장할 caseVec도 만들어주었다.

모든 CCTV의 방향을 전부 고려해야 하므로, dfs 함수에서는 각 CCTV에 대해 방향을 반복문을 통해

넣어주었고, 모든 CCTV의 방향을 입력했을 때, watchCCTV 함수를 통해 계산해주었다.

watchCCTV 함수

caseVec에 각 CCTV의 방향 정보가 들어있으므로, 이를 방향으로 하여 모든 CCTV에 대해 watch

함수를 적용하여 사무실의 감시 영역을 채운 후, 사각지대를 계산한다. 이 때, 동서남북 방향은 dx, dy

배열로 처리하였다.

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

🧩 코드