[BOJ]15683번: 감시

단순구현문제

#include <iostream>
#include <vector>
#include <algorithm>
 
 
const int MAX = 10;
const int VISITED_NUM = 9;
 
int check[MAX][MAX];
int plate[MAX][MAX];
bool visited[MAX][MAX];
std::vector<std::pair<int, int>> cctv_position;
int N, M;
int count, zero_size;
int min_size = 0;
bool Q, W, E, R;
 
 
void fill_plate(int y_position, int x_position, char dir) {
    int pos_x, pos_y;
 
    pos_x = x_position;
    pos_y = y_position;
 
    while (pos_x >= 0 && pos_x < M && pos_y >= 0 && pos_y < N) {
        if (plate[pos_y][pos_x] == 6) {
            break;
        }
        if (plate[pos_y][pos_x] == 0) {
            plate[pos_y][pos_x] = VISITED_NUM;
            check[pos_y][pos_x] = VISITED_NUM;
        }
 
        switch (dir) {
        case 'Q':
            pos_y--;
            break;
        case 'W':
            pos_x++;
            break;
        case 'E':
            pos_y++;
            break;
        case 'R':
            pos_x--;
            break;
        default:
            break;
        }
    }
}
 
void check_dir(int num, int start) {
    if (num == 2) {
        if ((start + 1) % 2 == 0) {
            Q = true, E = true;
        }
        else {
            W = true, R = true;
        }
 
        return;
    }
 
    if (num > 2) { num--; }
    for (int i = start; i < start + num; i++) {
        switch (i % 4) {
        case 0:
            Q = true;
            break;
        case 1:
            W = true;
            break;
        case 2:
            E = true;
            break;
        case 3:
            R = true;
            break;
        default:
            break;
        }
    }
}
 
void reset_arr_int(int arr[][MAX]) {
    for (int i = 0; i < N; i++) {
        std::fill(arr[i], arr[i] + MAX, 0);
    }
}
 
void reset_arr_bool(bool arr[][MAX]) {
    for (int i = 0; i < N; i++) {
        std::fill(arr[i], arr[i] + MAX, false);
    }
}
 
void plate_change(int change_plate[][MAX], int original_plate[][MAX]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            change_plate[i][j] = original_plate[i][j];
        }
    }
}
 
void count_zero(void) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (plate[i][j] == 0) { zero_size++; }
        }
    }
}
 
void DFS(int count) {
 
    if (count >= cctv_position.size()) { return; }
 
    int pre_plate[MAX][MAX];
    plate_change(pre_plate, plate);
    int y = cctv_position[count].first;
    int x = cctv_position[count].second;
 
 
    for (int j = 0; j < 4; j++) {
        Q = W = E = R = false;
        zero_size = 0;
 
        check_dir(plate[y][x], j);
        if (Q) { fill_plate(y, x, 'Q'); }
        if (W) { fill_plate(y, x, 'W'); }
        if (E) { fill_plate(y, x, 'E'); }
        if (R) { fill_plate(y, x, 'R'); }
 
        count_zero();
        min_size = min_size > zero_size ? zero_size : min_size;
 
        DFS(count + 1);
 
        plate_change(plate, pre_plate);
    }
}
 
int main(void) {
    std::cin >> N >> M;
    reset_arr_int(plate);
    reset_arr_bool(visited);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            std::cin >> plate[i][j];
            if (plate[i][j] == 0) { min_size++; }
            else if (plate[i][j] < 6) {
                cctv_position.push_back({ i, j });
            }
        }
    }
 
    DFS(0);
 
    std::cout << min_size << "\n";
    return 0;
}