[백준][15683] 감시

이 포스트는 백준 사이트의 감시 문제 풀이입니다.

문제

해결 과정

이 문제에서 핵심은 CCTV 회전과 그에 따른 사각지대 개수입니다.

이 문제를 해결하고자 먼저 CCTV 의 방향을 어떻게 구현할지 고민 중
기존에 사용하는 방법인 dir_row, dir_col 배열을 활용해보기로 했습니다.

5가지의 CCTV 는 각각 4가지 방향 중 최대 4개만 사용하므로
2차원 벡터를 활용하여 CCTV 가 감시하는 방향을 표현하였습니다.(변수명: cctv_type)
방향 표시는 위에서 언급한 dir_row, dir_col 에서 각 원소가 상(인덱스: 0), 우(1), 하(2), 좌(3) 순서이므로
문제에서 제시된 각 CCTV 의 현재 방향을 0으로 생각하고
0, 1, 2, 3 을 사용해 cctv_type 의 각 방향 정보를 저장하였습니다.

마지막으로 CCTV 를 회전시키기 위해서

((현재방향(0~3)) + (CCTV 회전방향(0~3))) % 4

위 수식을 사용해서 새로운 방향에 따라 감시되는 영역을 구하고
CCTV 개수와 벽 개수를 제외한 빈 공간 수 total_area에서
감시되는 영역을 뺸 값인 hidden_area 를 출력하였습니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

// 12시 방향에서 시계방향 순서대로 4가지 방향
int dir_row[4]{ -1, 0, 1, 0 };
int dir_col[4]{ 0, 1, 0, -1 };

int total_area, hidden_area = 2e9;

// 행, 열, cctv 타입, 회전 방향
struct POINT {
    int row, col, type, dir;
};

int N, M;
vector<vector<int>> board;

// 1번부터 5번까지 cctv의 감시 방향
vector<vector<int>> cctv_type{
    {},
    {1},
    {1, 3},
    {0, 1},
    {0, 1, 3},
    {0, 1, 2, 3}
};

void input(vector<POINT>& cctv);
void set_watching_area(vector<POINT>& cctv,
    vector<vector<bool>>& visited, POINT& camera);
int count_hidden_area(vector<POINT>& cctv);
void DFS(vector<POINT> cctv, int curr);

int main() {
    vector<POINT> cctv;
    input(cctv);

    DFS(cctv, 0);

    printf("%d", hidden_area);

    return 0;
}

void input(vector<POINT>& cctv) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    board.assign(N, vector<int>(M, 0));
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < M; ++col) {
            cin >> board[row][col];
            if (board[row][col] != 0
                && board[row][col] != 6) {
                cctv.push_back({ row, col, board[row][col], 0 });
            }
            if (board[row][col] == 0) {
                total_area += 1;
            }
        }
    }
}

void DFS(vector<POINT> cctv, int curr) {
    if (curr == cctv.size()) {
        hidden_area = min(hidden_area, count_hidden_area(cctv));
        return;
    }

    if(cctv[curr].type == 5) {
        DFS(cctv, curr + 1);
    } else {
        int prev_dir = cctv[curr].dir;
        for (int dir = 0; dir <= 3; ++dir) {
            cctv[curr].dir = dir;
            DFS(cctv, curr + 1);
        }
        cctv[curr].dir = prev_dir;
    }
}

int count_hidden_area(vector<POINT>& cctv) {
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    for (POINT camera : cctv) {
        set_watching_area(cctv, visited, camera);
    }

    int watching_tile_cnt = 0;
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < M; ++col) {
            if (board[row][col] == 6) continue;
            else if (visited[row][col]) {
                watching_tile_cnt += 1;
            }
        }
    }

    return (total_area - watching_tile_cnt > 0 ?
        total_area - watching_tile_cnt : 0);
}

void set_watching_area(vector<POINT>& cctv,
    vector<vector<bool>>& visited, POINT& camera) {
    for (int dir : cctv_type[camera.type]) {
        dir = (dir + camera.dir) % 4;

        for (int dist = 1; dist < max(N, M); ++dist) {
            int new_row = camera.row + dir_row[dir] * dist;
            int new_col = camera.col + dir_col[dir] * dist;

            if (new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if (board[new_row][new_col] == 6)
                break;
            if (board[new_row][new_col] == 0) {
                visited[new_row][new_col] = true;
            }
        }
    }
}

실행 결과