(C++) - 백준(BOJ) 15683번 : 감시 답

www.acmicpc.net/problem/15683

15683번: 감시

시뮬레이션 문제였습니다.

 

풀이방법

 1. 초기화 : 카메라의 개수를 구합니다 1 ~ 5사이에 있는 수들의 개수를 세준다면 카메라의 개수입니다. 이 때 회전상태를 저장할 수 있는 구조체를 만들어 x번째 카메라가 저장되어 있는 행,열의 좌표와 카메라의 종류 회전상태를 저장해줍니다.

 2. 각 카메라의 회전횟수(상태)를 모두 확인해줍니다. 

   0번에서 ~ 1<<(2 * 카메라개수)의 범위를 잡는다면 모든 카메라의 회전상태를 확인해볼 수 있습니다. 각 종류의 카메라는 모두 동,서,남,북으로 회전할 수 있으므로 최대 4^카메라개수의 상태가 존재합니다. 따라서 4진수로 표현될 수 있고 상기와 같이 표현했습니다. 매 상태 때마다 원본 사무실 상태를 복사해온 다음 감시카메라의 사각지대를 계산해줍니다.

   2-1. 카메라 전체의 회전 횟수로부터 각 카메라의 회전상태를 구해야합니다. j번째 카메라의 회전횟수는 (전체 회전상태 i % 4) 한 것이 됩니다. 예를 들어 8개의 카메라의 회전상태가 다음과 같다고 생각해봅시다. 1 2 3 1 1 2 2 1이라면 

4^7 * 1 + 4^6 * 2 + 4^5 * 3 + 4^4 * 1 + 4^3 * 1 + 4^2 * 2 + 4^1 * 2 + 4^0 + 1 = 전체 회전상태 입니다. 

sum(4^(전체카메라개수 - j번째 카메라) * j번째 카메라의 회전횟수) = i 로 정리할 수 있습니다. 이는 각 카메라의 회전상황이 0,1,2,3(동,서,남,북)의 비트로 표현될 수 있으니 4진법 입니다. for(j=0 ~ 카메라개수)로 루프문을 만들게 되면 매번 j번째 카메라의 회전횟수 = i%4를 한 뒤 i/=4를 해준다면 곧 j번째 카메라의 회전횟수를 구할 수 있습니다.

  2-2. j번째 카메라의 종류별로 감시할 수 있는 영역을 계산하고 사각지대를 계산합니다.

       한 방향으로 벽을 만날 때까지 감시했다를 표현하기 위해 영역을 정의한 상수 INF(약 10억)를 사용합니다. inputArea라는 함수를 정의해 방향에 따라 해당 방향으로 영역을 INF로 색칠해줍니다. 카메라 별로 inputArea의 호출 개수가 다릅니다. 1번 카메라는 1번, 2번 카메라는 2번,..., 5번카메라는 4번 입니다. 방향은 회전횟수를 알고있으므로 적절히 함수를 호출해 감시영역을 표시합니다. 이 후 사각지대를 계산한 뒤 최소값을 저장합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
using pii = pair<int,int>;
int office[10][10];
int origin[10][10];
int ans;
int n,m;

//좌, 상, 우, 하
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

struct info{
    int x,y,category,rotateNum;
};


void inputArea(int dir, int x, int y){
    while(1) {
        x += dx[dir];
        y += dy[dir];
        if(x < 0 || x >= n || y < 0 || y >=m) break;
        if(office[x][y]==6) break;
        if(office[x][y]!=0) continue; 
        office[x][y] = INF;
    }
}

void copyOffice(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            office[i][j] = origin[i][j];
        }
    }
}

int getVoidedArea(){
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!office[i][j]) cnt++;
        }
    }
    return cnt;
}

int main(){
    cin >> n >> m;
    int cameraNum = 0;
    int ans = 0;
    vector<info> cameraStat(8);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) {
            cin >> origin[i][j];
            if(!origin[i][j])ans++;
            if(origin[i][j]!=0 && origin[i][j] != 6) {
                cameraStat[cameraNum].x = i;
                cameraStat[cameraNum].y = j;
                cameraStat[cameraNum].category = origin[i][j];
                cameraStat[cameraNum].rotateNum = 0;
                cameraNum++;
            }
        }
    }
    for(int i = 0; i < (1<<(2*cameraNum)); i++ ){
        copyOffice();
        int num = i;
        for(int j = 0; j < cameraNum; j++){
            cameraStat[j].rotateNum = num % 4;
            num/=4;
            switch(cameraStat[j].category){
                case 1: 
                    inputArea((2+cameraStat[j].rotateNum)%4, cameraStat[j].x, cameraStat[j].y);
                    break;
                case 2:
                    //좌, 우
                    inputArea(cameraStat[j].rotateNum,cameraStat[j].x,cameraStat[j].y);
                    inputArea((2+cameraStat[j].rotateNum)%4,cameraStat[j].x,cameraStat[j].y);
                    break;
                case 3:
                    //상, 우
                    inputArea((1+cameraStat[j].rotateNum)%4,cameraStat[j].x,cameraStat[j].y);
                    inputArea((2+cameraStat[j].rotateNum)%4,cameraStat[j].x,cameraStat[j].y);
                    break;
                case 4:
                    for(int i=0;i<3;i++){
                        inputArea((i+cameraStat[j].rotateNum) %4 , cameraStat[j].x, cameraStat[j].y);
                    }
                    break;
                case 5:
                    for(int i=0;i<4;i++)
                        inputArea(i, cameraStat[j].x, cameraStat[j].y);
                    break;
            }

            ans = min(ans,getVoidedArea());
        }
    }
    cout << ans <<'\n';
}