[백준 15683]감시

감시

A. 접근법

Greedy하게 하나의 CCTV가 최대한 많은 곳을 감시하면 사각지대가 최소화 될 것으로 생각하고 접근하였습니다.

하지만 생각하다보니 Greedy로 풀 시 만약에 동일한 곳의 양을 감시한다고 판단을 할 때, 한 쪽 방향을 선택해서 탐색을 합니다. 이후 존재하는 CCTV와 동일한 곳을 감시한다고 하면 손해가 되기 때문에 접근 방법을 바꾸어 모든 방법을 탐색하여 사각지대가 최소화 되는 답을 얻어겠다고 판단 했습니다.

예시)
4 4
1 0 0 0
0 0 0 0
0 0 6 4
0 0 0 0

위와 같은 경우에서 1은 동쪽으로나 남쪽으로나 감시 가능한 영역이 같지만 이후 나오는 4의 방향이 최선을 결과를 내기 위해서는 4의 방향이 결정되어있기 때문에 1은 남쪽으로 감시하는 것이 사각지대를 최소화합니다.

따라서 1이 감시하는 영역이 동쪽으로 결정한 후 탐색을 하면 최선의 결과를 얻지 못하게 됩니다.

B. 구현

C. 코드

#include <iostream>
#include <vector>

using namespace std;
int N, M;
int T;
int i, j;
vector<vector<int>> v;
int answer = 99999999;

// goXXXX는 해당 방향으로 빈칸인 경우 -1로 바꿔서 감시되는 영역이라고 표시한다. 벽을 만나면 종료.
void goEast(int x, int y, vector<vector<int>>& v) {
    for(int a = y + 1; a < M; a++) {
        if(v[x][a] == 0)
            v[x][a] = -1;
        else if(v[x][a] == 6)
            break;
    }
}

void goWest(int x, int y, vector<vector<int>>& v) {
    for(int a = y - 1; a >= 0; a--) {
        if(v[x][a] == 0)
            v[x][a] = -1;
        else if(v[x][a] == 6)
            break;
    }
}

void goSouth(int x, int y, vector<vector<int>>& v) {
    for(int a = x + 1; a < N; a++) {
        if(v[a][y] == 0)
            v[a][y] = -1;
        else if(v[a][y] == 6)
            break;
    }
}

void goNorth(int x, int y, vector<vector<int>>& v) {
    for(int a = x - 1; a >= 0; a--) {
        if(v[a][y] == 0)
            v[a][y] = -1;
        else if(v[a][y] == 6)
            break;
    }
}

void solver(int i, vector<vector<int>> tv) {
    int a, b;

    if(i == M * N) {
        int cnt = 0;
        for(a = 0; a < N; a++) {
            for(b = 0; b < M; b++) {
                if(tv[a][b] == 0)
                    cnt++;
            }
        }

        if(cnt < answer)
            answer = cnt;
        return;
    }
    int x = i / M;
    int y = i % M;

    vector<vector<int>> tv1(tv);
    vector<vector<int>> tv2(tv);
    vector<vector<int>> tv3(tv);
    vector<vector<int>> tv4(tv);

    switch(tv[x][y]) {

        case 1:

            goEast(x, y, tv1);
            solver(i + 1, tv1);

            goWest(x, y, tv2);
            solver(i + 1, tv2);

            goSouth(x, y, tv3);
            solver(i + 1, tv3);

            goNorth(x, y, tv4);
            solver(i + 1, tv4);

            break;

        case 2:

            goEast(x, y, tv1);
            goWest(x, y, tv1);
            solver(i + 1, tv1);

            goSouth(x, y, tv2);
            goNorth(x, y, tv2);
            solver(i + 1, tv2);

            break;

        case 3:

            goNorth(x, y, tv1);
            goEast(x, y, tv1);
            solver(i + 1, tv1);

            goEast(x, y, tv2);
            goSouth(x, y, tv2);
            solver(i + 1, tv2);

            goSouth(x, y, tv3);
            goWest(x, y, tv3);
            solver(i + 1, tv3);

            goWest(x, y, tv4);
            goNorth(x, y, tv4);
            solver(i + 1, tv4);

            break;

        case 4:

            goEast(x, y, tv1);
            goWest(x, y, tv1);
            goSouth(x, y, tv1);
            solver(i + 1, tv1);

            goEast(x, y, tv2);
            goWest(x, y, tv2);
            goNorth(x, y, tv2);
            solver(i + 1, tv2);

            goEast(x, y, tv3);
            goSouth(x, y, tv3);
            goNorth(x, y, tv3);
            solver(i + 1, tv3);

            goWest(x, y, tv4);
            goSouth(x, y, tv4);
            goNorth(x, y, tv4);
            solver(i + 1, tv4);

            break;

        case 5:
        
            goEast(x, y, tv1);
            goWest(x, y, tv1);
            goSouth(x, y, tv1);
            goNorth(x, y, tv1);
            solver(i + 1, tv1);
            
            break;
            
        default:
        
            solver(i + 1, tv);
            
            break;
    }


}
int main() {
    //scanf("%d", &T);
    T = 1;

    for(int tc = 0; tc < T; tc++) {
        scanf("%d %d", &N, &M);
        v.clear();
        v.resize(N);
        answer = 99999999;
        int tmp;
        for(i = 0; i < N; i++) {
            for(j = 0; j < M; j++) {
                scanf("%d", &tmp);
                v[i].push_back(tmp);
            }
        }

        solver(0, v);

        printf("%d\n", answer);
    }
    return 0;
}

D. 결과