백준 15683 감시

예제가 많아서 조금 짤렸다..

 

오랜만에 시간 안에 푼 문제이다. 1시간 40분 정도 걸려서 푼 것 같다. 처음부터 손으로 정리를 하고 풀었더니 문제가 쉬운 건지 모르겠으나 비교적 쉽게 풀었던 것 같다.

 

1. 오른쪽으로 쭉 감시 방향을 체크하는 함수, 왼쪽, 위, 아래로 감시하는 함수를 각각 만들었다. 처음에는 하나의 dfs 함수에 다 구현하려 했으나 너무 같은 코드가 반복되어 함수로 따로 만들어 주었다.

그랬더니 cctv의 종류에 따라 맞는 함수만 골라 쓰면 되어서 편하게 구현할 수 있었다.

 

2. 재귀로 구현되기 때문에 종료 조건이 있어야 한다. 선택한 cctv의 개수가 총 cctv의 개수와 일치하면 사각지대의 수를 ans vector에 넣는다.(나중에 최소값을 찾기 위해 사각지대 수를 넣어둔다.)

이 문제는 cctv를 선택하고 안하고의 문제가 아니라, 방향을 선택하고 방향을 선택했을 시 다음 선택된 cctv의 방향을 선택하는 문제이다. 순열로 이해하면 될 것 같다.

 

3. 시간 복잡도를 구하는 것이 항상 힘들었는데, 8(N) X 8(M) X 4^8(1번 cctv일 때 방향의 개수, cctv는 최대 8대)라고 생각하고 구했더니 4백만 정도가 나와서, 완전탐색이 가능하다고 생각했다.

 

4. 감시 가능한 영역을 -1만 대입했더니 여러 대의 cctv 감시 영역이 겹치는 경우가 발생했다. 3대의 cctv가 감시 할 수 있는 영역인데, 하나의 cctv가 재귀가 끝나서 해당 원소를 0으로 바꿔버리면 문제가 발생하는 것이다.

그래서 빈칸 영역이 감시 영역이 될 때마다 -1을 대입하는 것이 아니라 1을 빼줘서 몇 번 겹치는지를 체크하였다.

 

코드는 아래와 같다.

줄인다고 줄였는데 그래도 길다. 나중에 리팩토링을 통해서 줄여봐야겠다. 다른 분들 코드도 참조하면서..

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
 
void solve(int idx);
 
int office[8][8];
int n, m;
 
vector<tuple<int, int, int>> cctvs;
vector<int> ans;
 
int cal() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //0인 부분이 사각지대이다.
            if (office[i][j] == 0)res++;
        }
    }
    /*출력(디버깅)
    printf("\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%2d ", office[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    */
    return res;
}
 
void ret_del(vector<pair<int, int>> &ret) {
    //다음 방향을 보기 위해서 감시영역을 지워준다.
    for (int i = 0; i < ret.size(); i++) {
        int r = ret[i].first;
        int c = ret[i].second;
        
    office[r][c]++;
    }
    ret.clear();
}
 
void left(int row, int col, vector<pair<int,int>> &ret, int idx) {
    //왼쪽으로
    for (int i = col; i >= 0; i--) {
        if (office[row][i] == 6)break;
        if (office[row][i] == 1 || office[row][i] == 2 || office[row][i] == 3 || office[row][i] == 4 || office[row][i] == 5) continue;
        office[row][i]--;
        ret.push_back(make_pair(row, i));
    }
}
 
void right(int row, int col, vector<pair<int, int>> &ret, int idx) {
    //오른쪽
    for (int i = col; i < m; i++) {
        //다른 cctv도 지나갈 수 있기 때문에 벽만 break한다.
        if (office[row][i] == 6)break;
        //다른 cctv면 지나간다.
        if (office[row][i] == 1 || office[row][i] == 2 || office[row][i] == 3 || office[row][i] == 4 || office[row][i] == 5) continue;
        //감시 영역을 --시켜준다. -1로 설정하니까 겹치는 부분 복귀를 못시킴.
        office[row][i]--;
        ret.push_back(make_pair(row, i));
    }
}
 
void up(int row, int col, vector<pair<int, int>> &ret, int idx) {
    for (int i = row; i >= 0; i--) {
        if (office[i][col] == 6)break;
        if (office[i][col] == 1 || office[i][col] == 2 || office[i][col] == 3 || office[i][col] == 4 || office[i][col] == 5) continue;
        office[i][col]--;
        ret.push_back(make_pair(i, col));
    }
}
 
void down(int row, int col, vector<pair<int, int>> &ret, int idx) {
    for (int i = row; i < n; i++) {
        if (office[i][col] == 6)break;
        if (office[i][col] == 1 || office[i][col] == 2 || office[i][col] == 3 || office[i][col] == 4 || office[i][col] == 5) continue;
        office[i][col]--;
        ret.push_back(make_pair(i, col));
    }
}
 
void solve(int idx) {
    //모든 cctv를 다 골랐을 때
    if (idx == cctvs.size()) {
        //사각지대를 다 계산한다.
        ans.push_back(cal());
        return;
    }
    //cctv 자체를 선택하고 안하고가 아니라, 방향을 선택하고 안하고 이기 때문에 다른 종료 조건은 필요없다.(cctv 총 개수를 인자로 전달할 필요가 없다.)
    int row, col, ver;
    tie(row, col, ver) = cctvs[idx];
 
    //-1로 설정한 것을 되돌리기 위한 vector가 필요하다.
    vector<pair<int, int>> ret;
    switch (ver) {
    case 1://4가지 방향이 있다.
        //감시영역 표시를 위한 함수들
        left(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        right(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        up(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        down(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        break;
    case 2:
        //좌우로
        left(row, col, ret, idx);
        right(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //아래위
        up(row, col, ret, idx);
        down(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        break;
    case 3:
        //위, 오른쪽
        up(row, col, ret, idx);
        right(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //오른쪽, 밑
        right(row, col, ret, idx);
        down(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //밑, 왼쪽
        down(row, col, ret, idx);
        left(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //왼쪽, 위
        left(row, col, ret, idx);
        up(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        break;
    case 4:
        //왼쪽 위 오른쪽
        left(row, col, ret, idx);
        up(row, col, ret, idx);
        right(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //위 오른쪽 밑
        up(row, col, ret, idx);
        right(row, col, ret, idx);
        down(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //오른쪽 밑 왼쪽
        right(row, col, ret, idx);
        down(row, col, ret, idx);
        left(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        //밑 왼쪽 위
        down(row, col, ret, idx);
        left(row, col, ret, idx);
        up(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        break;
    case 5:
        //전방향
        up(row, col, ret, idx);
        right(row, col, ret, idx);
        down(row, col, ret, idx);
        left(row, col, ret, idx);
        solve(idx + 1);
        ret_del(ret);
        break;
    }
}
 
int main(int argc, char** argv) {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &office[i][j]);
            //cctv 정보들을 저장한다. 나중에 재귀에서 쓰기 위해
            if (office[i][j] != 0 && office[i][j] != 6)cctvs.push_back(make_tuple(i, j, office[i][j]));
        }
    }
 
    solve(0);
 
    printf("%d\n", *min_element(ans.begin(), ans.end()));
 
    return 0;
}