#15683 감시

문제 링크 : https://www.acmicpc.net/problem/15683

15683번: 감시

 

딱 봐도 Brute-force로 풀리는 문제다. 구현하는게 번거로울 것 같다만..

 

 

일단 cctv의 유형에 따라 볼 수 감시할 수 있는 방향의 차이가 있기에 이를 먼저 어떻게 처리할지 생각해야 한다.

 

cctv가 보는 방향을 바꿀 수도 있기 때문에 방향까지 고려해줘야 한다.

 

cctv의 타입에 따라, cctv의 방향에 따라, 감시할 수 있는 방향들을 3차원 백터의 형태로 만들어 사용할 수 있을 것이다.

// (북, 동, 남, 서) = (0, 1, 2, 3)
// 각각 cctv가 북, 동, 남, 서를 볼 때 감지 가능한 방향
{ 
   { {0}, {1}, {2}, {3} }, // Type 1
   { {0, 2}, {1, 3}}, // Type 2
   { {0, 1}, {1, 2}, {2, 3}, {3, 0}}, // Type 3
   { {0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}}, // Type 4
   { {0, 1, 2, 3} } // Type 5
}

 

아니면 약간의 중복이 있겠지만 방향을 돌리는 로직을 감시 가능한 영역을 확인할 때 추가한다면 2차원 백터로도 충분하다.

// (북, 동, 남, 서) = (0, 1, 2, 3)
{ 
   {0}, // Type 1
   {0, 2}, // Type 2
   {0, 1}}, // Type 3
   {0, 1, 2}, // Type 4
   {0, 1, 2, 3} // Type 5
}

// 이 다음 다른 방향들을 고려할 때
// 0부터 3까지 더해주며 (모듈러 연산 필요) 방향 전환

 

그 다음 실제로 감시 가능한 영역을 확인하여 사각 지대의 최소값을 구해야 한다.

 

recursive function 을 만드는 게 편할 것 같다는 생각이 든다.

 

감시 가능한지 여부를 썼다 지웠다 하는 건 힘든 일이기 때문에 현재 상태를 vector 형태로 그대로 넘겨 줄 것이다.

(reference 사용 x, 고대로 넘겨줘서 copy 해야함)

 

 

대충 계산했을 때, 최대 cctv의 개수 8, 최대 가로, 세로 길이 8, 고려해야 하는 cctv의 방향 경우의 수 4 이므로

 

Time Complexity $$O((8 + 8) * 4^8) = O(2^{20}) \approx O(10^7) $$

 

넉넉하다.

 

메모리도 대충 $$4^8 * 8 * 8 * 4 = 2^{24} \text{Bytes} = 16 \text{MB}$$

 

정도로 충분할 것으로 보인다.

 

 

코드는 나중에 짜야지

 

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int> > state(8, vector<int>(8));
int dir_x[] = {0, 1, 0, -1}, dir_y[] = {-1, 0, 1, 0};
vector<pair<int, int> > cctv_dir{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
vector<vector<vector<int> > > cctv;
vector<pair<int, int> > cctv_pos;

void initiate_cctv() {
    vector<vector<int> > first;
    for (int i = 0; i < 4; i++) {
        vector<int> tmp{i};
        first.push_back(tmp);
    }
    cctv.push_back(first);

    vector<vector<int> > second;
    for (int i = 0; i < 2; i++) {
        vector<int> tmp{i, i + 2};
        second.push_back(tmp);
    }
    cctv.push_back(second);

    vector<vector<int> > third;
    for (int i = 0; i < 4; i++) {
        vector<int> tmp{i, (i + 1) % 4};
        third.push_back(tmp);
    }
    cctv.push_back(third);

    vector<vector<int> > fourth;
    for (int i = 0; i < 4; i++) {
        vector<int> tmp{i, (i + 1) % 4, (i + 2) % 4};
        fourth.push_back(tmp);
    }
    cctv.push_back(fourth);

    vector<vector<int> > fifth;
    vector<int> tmp;
    for (int i = 0; i < 4; i++) {
        tmp.push_back(i);
    }
    fifth.push_back(tmp);
    cctv.push_back(fifth);
}

bool cant_move(pair<int, int> pos) {
    int x = pos.first, y = pos.second;
    return ((x < 0) || (y < 0) || (x == m) || (y == n) || (state[x][y] == 6));
}

int perform_cctv(vector<vector<int> > &cur_state, pair<int, int> &cur_cctv,
                 int cur_dir) {
    int cur_x = cur_cctv.first, cur_y = cur_cctv.second;
    int cur_type = state[cur_x][cur_y] - 1;
    int ret = 0;

    for (auto dir : cctv[cur_type][cur_dir]) {
        int new_x = cur_x + dir_x[dir];
        int new_y = cur_y + dir_y[dir];

        while (!cant_move({new_x, new_y})) {
            if (cur_state[new_x][new_y] == 0) {
                cur_state[new_x][new_y] = -1;
                ret++;
            }
            new_x += dir_x[dir];
            new_y += dir_y[dir];
        }
    }

    return ret;
}

int perform_cctvs(vector<vector<int> > cur_state) {
    if (cctv_pos.empty()) {
        return 0;
    }

    pair<int, int> cur_cctv = cctv_pos.back();
    int cctv_x = cur_cctv.first, cctv_y = cur_cctv.second;
    int cctv_type = state[cctv_x][cctv_y] - 1;
    cctv_pos.pop_back();

    int max_check_cnt = 0, check_cnt;
    for (int cctv_dir = 0; cctv_dir < cctv[cctv_type].size(); cctv_dir++) {
        check_cnt = 0;
        vector<vector<int> > tmp_state(cur_state.begin(), cur_state.end());

        check_cnt += perform_cctv(tmp_state, cur_cctv, cctv_dir);
        check_cnt += perform_cctvs(tmp_state);
        max_check_cnt = max(max_check_cnt, check_cnt);
    }

    cctv_pos.push_back(cur_cctv);

    return max_check_cnt;
}

int main() {
    int wall_cnt = 0;
    initiate_cctv();

    scanf("%d %d", &n, &m);

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            scanf("%d", &state[x][y]);

            if (1 <= state[x][y] && state[x][y] <= 5) {
                cctv_pos.push_back({x, y});
            } else if (state[x][y] == 6) {
                wall_cnt++;
            }
        }
    }

    int ret = n * m - wall_cnt - perform_cctvs(state) - cctv_pos.size();
    printf("%d", ret);

    return 0;
}

 

확실히 연습을 하지 않으니 실력이 많이 녹슬어서 생각보다 코드 짜는데 시간이 오래 걸렸다.

 

다른 사람들은 시간을 어떻게 줄였는지 참고해야겠다.

 

 

 

cctv 를 순회하는 것을 나는 pop_back(), push_back() 으로 처리해줬는데 그냥 인덱스만 있어도 충분했다...

시간을 조금 단축시켰다

나머지는 구조상의 문제인듯 하다. 이차원 백터를 계속 복사해서 그런듯.