백준 15683번: 감시

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

반례 모음 : https://www.acmicpc.net/board/view/26220

5가지 종류의 cctv가 주어지고, 사무실 정보가 주어졌을 때 사각지대의 최소 크기를 구하는 문제이다.

<틀린 방법>
처음에는 한 cctv마다 4방향으로 볼 수 있는 좌표를 구해서 저장을 하고, cctv 번호에 따라서 최대로 볼 수 있는 개수가 있는 방향으로 감시를 하도록 했다.

설명을 되게 못썼는데, 예시로 설명을 해 보겠다.
1번 카메라 : 값 = 1, 방향별 감시할 수 있는 공간의 수 = 0 1 2 3 (상 하 좌 우 순서로 했다.)
2번 카메라 : 값 = 4, 방향별 감시할 수 있는 공간의 수 = 2 3 0 1

이렇게 두 개의 cctv가 있다고 할 때, 1번 카메라는 값이 1이므로 한 방향만 볼 수 있으므로 가장 많은 공간을 감시할 수 있는 오른쪽으로 고개를 틀어 3개의 공간을 감시하도록 설정한다.
2번 카메라는 값이 4이므로 총 3방향을 볼 수 있으므로 0개의 공간을 감시하는 왼쪽을 제외한 나머지 3방향을 감시하도록 설정했다.

항상 최대로 감시하는 경우로 세팅을 해서 코드를 작성하고 문제에서 주어진 테스트케이스는 전부 통과하여 제출을 했으나 바로 '틀렸습니다'가 떴다. 그리디한 방법인 것 같은데, 완전 탐색 문제라 통하지 않았나보다.


<맞은 방법>
구글링을 해서 코드는 참고하지 않고, 모든 카메라의 모든 방향을 체크해서 모든 경우의 수를 전부 순회한 뒤, 그 중 최소 크기의 사각지대를 구하도록 다시 코드를 짰다.

각 cctv마다 4방향으로 볼 수 있는 좌표를 구하는 것은 동일하되 그 이후에 cctv의 값에 따라 보는 방향을 백트래킹으로 전부 다 보도록 처리했더니 정답 처리되었다. 즉, 이전에는 내가 생각했을 때 최적의 경우만 체크를 했다면 완전 탐색으로 전부 다 순회하니 맞을 수 있었다.

예시로 설명하면,
1번 카메라가 '동쪽'을 보게 세팅, 2번 카메라가 '동서남'을 보게 세팅 -> 이때 사각지대 수 체크
1번 카메라는 그대로, 2번 카메라가 '동서북'을 보게 세팅 -> 사각지대 수
1번 카메라는 그대로, 2번 카메라가 '동남북'을 보게 세팅 -> 사각지대 수
1번 카메라는 그대로, 2번 카메라가 '서남북'을 보게 세팅 -> 사각지대 수

1번 카메라가 '서쪽'을 보게 세팅, 2번 카메라가 '동서남'을 보게 세팅 -> 사각지대 수
...
등으로 모든 경우의 수를 순회할 수 있도록 했다.

참고로 cctv의 숫자에 따라서
1 : ←, ↑, →, ↓ 4가지
2 : ←→, ↑↓ 2가지
3 : ←↑, ←↓, →↑, →↓ 4가지
4 : ←↑→, ↑→↓, →↓←, ←↓↑ 4가지
5 : ←↑→↓ 1가지

이렇게 경우의 수가 있다. 전부 코드로 처리해주면 된다!

<작성한 코드>

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define min(a, b) (a < b ? a : b)
using namespace std;

int n, m, result = 100;
int board[9][9];
int dx[4] = {-1, 1, 0, 0}; // 상 하 좌 우
int dy[4] = {0, 0, -1, 1};
vector<pair<int, int>> v; // cctv 위치 저장

int blindSpot(){ // 사각지대
    int cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(board[i][j] == 0)
                cnt++;
    return cnt;
}

void changeBoard(queue<pair<int, int>> q, int val){
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        board[x][y] = val;
    }
}

void dfs(int idx){
    if(idx == v.size()){
        result = min(result, blindSpot());
        return ;
    }
    int x = v[idx].first;
    int y = v[idx].second;
    queue<pair<int, int>> q[4];
    
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        while(0 <= nx && nx < n &&
        0 <= ny && ny < m &&
        board[nx][ny] != 6){
            if(board[nx][ny] == 0)
                q[i].push({nx, ny});
            nx += dx[i];
            ny += dy[i];
        }
    } // 4방향으로 볼 수 있는 모든 좌표 q에 저장
    
    if(board[x][y] == 1){
        for(int i = 0; i < 4; i++){
            changeBoard(q[i], -1);
            dfs(idx + 1);
            changeBoard(q[i], 0);
        }
    }
    else if(board[x][y] == 2){ // 수평, 수직 2방향
        for(int i = 0; i < 3; i += 2){
            changeBoard(q[i], -1);
            changeBoard(q[i + 1], -1);
            dfs(idx + 1);
            changeBoard(q[i], 0);
            changeBoard(q[i + 1], 0);
        }
    }
    else if(board[x][y] == 3){ // 4가지
        for(int i = 0; i < 2; i++){
            changeBoard(q[i], -1);
            for(int j = 2; j < 4; j++){
                changeBoard(q[j], -1);
                dfs(idx + 1);
                changeBoard(q[j], 0);
            }
            changeBoard(q[i], 0);
        }
    }
    else if(board[x][y] == 4){ // 3방향
        for(int i = 0; i < 4; i++){
            changeBoard(q[i], -1);
            changeBoard(q[(i + 1) % 4], -1);
            changeBoard(q[(i + 2) % 4], -1);
            dfs(idx + 1);
            changeBoard(q[i], 0);
            changeBoard(q[(i + 1) % 4], 0);
            changeBoard(q[(i + 2) % 4], 0);
        }
    }
    else{
        for(int i = 0; i < 4; i++)
            changeBoard(q[i], -1);
        dfs(idx + 1);
        for(int i = 0; i < 4; i++)
            changeBoard(q[i], 0);
    }
}

int main(){
    int cnt = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
            if(1 <= board[i][j] && board[i][j] <= 5)
                v.push_back({i, j});
        }
    
    dfs(0);
    cout << result;
}

풀 때는 몰랐는데 알고보니 삼성 기출문제.. 역시 구현하기 너무 까다롭다. 생각만 좀 더 잘 하면 그래도 풀 수 있을지도.. 화이팅이다