[ C++ ] #15683 감시 ( 골드 IV )

문제

---

사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다.

사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

 

풀이

---

각 번호의 cctv의 모든 경우의 수를 살펴봐야한다.

뭔가 다른 방법이 있나 했는데 그저 하나씩 확인해봐야하는게 답이었다.

내가 생각못했던 것은 4진수를 이용하는 것이다.

cctv의 개수만큼 4를 곱해주고 이를 이용하여 cctv의 방향을 체크한다.

각 자리의 숫자는 cctv의 방향을 가르킨다.

카메라가 3개일 때 0부터 63까지의 수를 4진법으로 나타내면 000, 001,… 332, 333까지 간다. 그리고 각각의 자리를 방향 3개에 대응시킨다. 중간의 39로 예를 들어보면 39는 4진수로 213이니까 방향을 (2, 1, 3)으로 둘 수 있습니다. 이렇게 하면 총 64가지의 모든 조합을 다 확인해볼 수 있다.

문제에서 나온 test case는 모두 맞았는데 계속 틀렸습니다!가 나왔다.

print를 찍어서 확인해보니 문제점을 금방 찾게되었다.

cctv가 찍는 방향을 check할 때 그냥 배열에서 0부터 M-1까지 체크하는 식으로 했는데 이렇게 하면 안되고 cctv에서부터 뻗어나가게 체크해야 벽이 막히는 것을 정확하게 체크할 수 있다는 것이었다.

 

#include <cmath>
#include <iostream>

using namespace std;

int N, M;
int map[10][10];
int check[10][10];
int cctv[10]; //cctv방향
int cnt; //cctv 개수

void right(int i, int j){   //cctv로 부터 right
    for(int a=j;a<M;a++){
        if(check[i][a]==6) break;
        check[i][a]=1;
    }
}

void down(int i, int j){
    for(int a=i;a<N;a++) {
        if(check[a][j]==6) break;
        check[a][j] = 1;
    }
}

void left(int i, int j){
    for(int a=j;a>=0;a--){
        if(check[i][a]==6) break;
        check[i][a]=1;
    }
}

void up(int i, int j){
    for(int a=i;a>=0;a--){
        if(check[a][j]==6) break;
        check[a][j]=1;
    }
}

int find(int temp){  //사각지대 찾기

    int num=0; //cctv 개수
    int t=temp; //temp의 temp

    //cctv 방향 설정
    for(int i=0;i<cnt;i++){
        cctv[i]=t%4;
        t=t/4;
    }

    for(int i=0;i<N;i++){ //cctv setting
        for(int j=0;j<M;j++){
            if(check[i][j]!=6) check[i][j]=0;;
        }
    }

    for(int i=0;i<N;i++){ //cctv 체크하기
        for(int j=0;j<M;j++){
            if(num==cnt){//모든 cctv를 다 돌면 나가기
                break;
            }
            int turn =map[i][j];
            if(turn>0&&turn!=6){ //cctv를 발견했다면
                if(turn==1){ //1번 cctv
                    if(cctv[num]==0){  //->
                        right(i,j);
                    }else if(cctv[num]==1){ //아래
                        down(i,j);
                    }else if(cctv[num]==2){ //<-
                        left(i,j);
                    }else if(cctv[num]==3){  // ^
                        up(i,j);
                    }
                }else if(turn==2){ //2번 cctv
                    if(cctv[num]==0){  //가로
                        right(i,j);
                        left(i,j);
                    }else if(cctv[num]==1) { //세로
                        down(i,j);
                        up(i,j);
                    }else{
                        down(i,j);
                        up(i,j);
                    }
                }else if(turn==3){ //3번 cctv

                    if(cctv[num]==0){  //^ ->
                        up(i,j);
                        right(i,j);
                    }else if(cctv[num]==1){ //-> 아래
                        right(i,j);
                        down(i,j);
                    }else if(cctv[num]==2){ //<- 아래
                        left(i,j);
                        down(i,j);
                    }else if(cctv[num]==3){  // <- ^
                        left(i,j);
                        up(i,j);
                    }

                }else if(turn==4) { //4번 cctv
                    if(cctv[num]==0){  //->
                        down(i,j);
                        up(i,j);
                        right(i,j);
                    }else if(cctv[num]==1){ //아래
                        right(i,j);
                        left(i,j);
                        up(i,j);
                    }else if(cctv[num]==2){ //<-
                        down(i,j);
                        up(i,j);
                        left(i,j);
                    }else if(cctv[num]==3){  // ^
                        right(i,j);
                        left(i,j);
                        down(i,j);
                    }

                }else if(turn==5){ //5번 cctv
                    right(i,j);
                    left(i,j);
                    down(i,j);
                    up(i,j);
                }
                num++;
            }
        }
    }

    num=0;

    for(int i=0;i<N;i++){ //개수새기
        for(int j=0;j<M;j++){
            if(check[i][j]<1){
                num++;
            }
        }
    }

    return num;

}

int main(){

    int min=10000;
    cin>>N>>M;

    //입력받기
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            int temp;
            cin>>temp;
            if(temp>0&&temp!=6){
                cnt++;
            }
            if(temp==6){
                check[i][j]=6; //벽
            }
            map[i][j]=temp;
        }
    }

    //모든 경우의 수 살펴보기
    for(int i=0;i<pow(4,cnt);i++){
        int temp=find(i);
        if(temp<min){
            min=temp;
        }
    }

    cout<<min;

    return 0;

}