[C++]감시[백준 15683]

그냥 1차원적인 구현 문제이다. 

감시카메라의 갯수가 8개를 넘지않으므로 

각 카메라에 대한 회전 경우의수 4가지 (0도 90도 180도 270도)

4^8 = O(65536 * n^2(사각지역을 구할때 8*8밖에 되지않아 그냥 0인곳을 매번 다 탐색했다))

본인은 구현하지 않았지만 생각해보면 다음 5번 경우는 회전을해도 그대로니 

               5번 케이스인 경우는 제외하고 탐색해준다면 더빠를것 같다. 

다른분들은 더 효율적으로 짠것같기는 한데 나는 무려 20MS나 나왔다... ㅠ

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

15683번: 감시

문제 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 2번 3번 4번 5번 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCT

www.acmicpc.net

<code>

//pda_pro12
#include<iostream>
#include<vector>
#define INT 0x7fff0000
using namespace std;
 
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, n, m;   // 0: 위 // 1: 오른 // 2: 아래 // 3: 왼 
bool Map[9][9][4]; int tmp[9][9], Orign[9][9];
vector<pair<int, int>> v;  // 감시카메라의 좌표정보 저장(1~8) 
vector<int> Rotate; // 카메라 회전정보 저장(O(4^v.size()))
int ans = INT;    // 최소값 산출을 위해 초기값 INT MAX값으로 214748347 설정
 
int Min(int a, int b) {
    return (a < b) ? a : b; 
}
 
int Recovery() {   // 감시처리 전의 상태로 복구함과 동시에 사각지역 탐색 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmp[i][j] == 0) cnt++;
            tmp[i][j] = Orign[i][j];
        }
    }
    return cnt;
}
 
void View_Camera(int num, int flag) {  // 몇번 카메라가 몇도 회전 했는지 Prameter로 받는다. 
    int x = v[num].first;  int y = v[num].second;
    for (int i = 0; i < 4; i++) {
        if (Map[x][y][i]) {
            int nx = x + dx[(i + flag) % 4];  int ny = y + dy[(i + flag) % 4];
            while (tmp[nx][ny] != 6 && nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위를 벗어나지 않거나 이미 감시한 지역(9)이고, 빈칸일경우 
                if (tmp[nx][ny] == 0) tmp[nx][ny] = 9;
                nx += dx[(i + flag) % 4];  ny += dy[(i + flag) % 4];
            }
        }
    }
    return;
}
 
void dfs(int cnt) {
    if (cnt == v.size()) { // 카메라에 대한 회전 정보가 카메라 갯수와 같아젔다면
        for (int i = 0; i < Rotate.size(); i++) // 회전정보만큼 카메라 돌려서 감시지역 처리해주기
            View_Camera(i, Rotate[i]);
        ans = Min(ans, Recovery());
        return;
    }
    for (int i = 0; i < 4; i++) { // 0: No rotate 1: 90  2: 180 3: 270
        Rotate.push_back(i);
        dfs(cnt + 1);
        Rotate.pop_back();
    }
    return;
}
 
int main() {
    cin >> n >> m;   // n = row  ,    m = col 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
            Orign[i][j] = tmp[i][j];
            if (!tmp[i][j] || tmp[i][j] == 6)     continue; // 0이나 벽일경우 
            v.push_back(make_pair(i, j));  // Camera Direction (row, col); 
 
            switch (tmp[i][j]) {  // No1 ~ No5 Camera Direction input
            case 1: // 1type Camera   --> 초기 방향에 대한 정보를 저장해둔다 
                Map[i][j][1] = true;
                break;
            case 2:    //2type Camera
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 3:  // 3type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                break;
            case 4:   // 4type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 5:
                for (int a = 0; a < 4; a++)
                    Map[i][j][a] = true;
                break;
            }
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}

< STL의 유혹을 떨처버린 Code >

//pda_pro12
#include<iostream>
#define INT 0x7fff0000
 
using namespace std;
 
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, n, m;   // 0: 위 // 1: 오른 // 2: 아래 // 3: 왼 
bool Map[9][9][4]; int tmp[9][9], Orign[9][9];
 
template<class T>
class _vector {
public:
    int _size; 
    int capacity; 
    T* arr; 
    _vector() {
        _size = 0; 
        capacity = 32; 
        arr = new T[capacity]; 
    }
    _vector(int k) {
        _size = k; 
        capacity = k; 
        arr = new T[k]; 
    }
    ~_vector() {
        delete[] arr; 
    }
    void clear() {
        delete[] arr; 
        _size = 0; 
        capacity = 32; 
        arr = new T[capacity]; 
    }
    
    void resize(int k) {
        T* temp; 
        temp = new T[k];
        for (int i = 0; i < _size; ++i) 
            temp[i] = arr[i]; 
        delete[] arr; 
        arr = temp; 
        _size = capacity = k; 
    }
 
    int size() const {
        return _size; 
    }
 
    T* begin() const {
        return &arr[0]; 
    }
 
    T* end() const {
        return &arr[0] + _size; 
    }
 
    void push_back(T val) {
        if (capacity == _size) {
            resize(_size * 2); 
            _size /= 2; 
        }
        arr[_size++] = val; 
    }
 
    void pop_back() {
        _size--; 
    }
 
    T& operator[](int idx) {
        return arr[idx]; 
    }
 
    T operator[](int idx) const{
        return arr[idx]; 
    }
};
 
_vector<pair<int, int>> v;  // 감시카메라의 좌표정보 저장(1~8) 
_vector<int> Rotate; // 카메라 회전정보 저장(O(4^v.size()))
 
int ans = INT;    // 최소값 산출을 위해 초기값 INT MAX값으로 214748347 설정
 
int Min(int a, int b) {
    return (a < b) ? a : b;
}
 
int Recovery() {   // 감시처리 전의 상태로 복구함과 동시에 사각지역 탐색 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmp[i][j] == 0) cnt++;
            tmp[i][j] = Orign[i][j];
        }
    }
    return cnt;
}
 
void View_Camera(int num, int flag) {  // 몇번 카메라가 몇도 회전 했는지 Prameter로 받는다. 
    int x = v[num].first;  int y = v[num].second;
    for (int i = 0; i < 4; i++) {
        if (Map[x][y][i]) {
            int nx = x + dx[(i + flag) % 4];  int ny = y + dy[(i + flag) % 4];
            while (tmp[nx][ny] != 6 && nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위를 벗어나지 않거나 이미 감시한 지역(9)이고, 빈칸일경우 
                if (tmp[nx][ny] == 0) tmp[nx][ny] = 9;
                nx += dx[(i + flag) % 4];  ny += dy[(i + flag) % 4];
            }
        }
    }
    return;
}
 
void dfs(int cnt) {
    if (cnt == v.size()) { // 카메라에 대한 회전 정보가 카메라 갯수와 같아젔다면
        for (int i = 0; i < Rotate.size(); i++) // 회전정보만큼 카메라 돌려서 감시지역 처리해주기
            View_Camera(i, Rotate[i]);
        ans = Min(ans, Recovery());
        return;
    }
    for (int i = 0; i < 4; i++) { // 0: No rotate 1: 90  2: 180 3: 270
        Rotate.push_back(i);
        dfs(cnt + 1);
        Rotate.pop_back();
    }
    return;
}
 
int main() {
    cin >> n >> m;   // n = row  ,    m = col 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
            Orign[i][j] = tmp[i][j];
            if (!tmp[i][j] || tmp[i][j] == 6)     continue; // 0이나 벽일경우 
            v.push_back(make_pair(i, j));  // Camera Direction (row, col); 
            switch (tmp[i][j]) {  // No1 ~ No5 Camera Direction input
            case 1: // 1type Camera   --> 초기 방향에 대한 정보를 저장해둔다 
                Map[i][j][1] = true;
                break;
            case 2:    //2type Camera
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 3:  // 3type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                break;
            case 4:   // 4type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 5:
                for (int a = 0; a < 4; a++)
                    Map[i][j][a] = true;
                break;
            }
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}