[백준-삼성SW역량테스트 기출] 15683번. 감시 C++

www.acmicpc.net/problem/15683

15683번: 감시

>문제 설명

 

풀이

완전 탐색 문제이다.

 

CCTV 최대 8개이고, 각 CCTV 번호 당 회전시킨 경우의 수는 아래와 같다.

• 1번: 4가지
• 2번: 2가지
• 3번: 4가지
• 4번: 4가지
• 5번 1가지

따라서 최대 4^8 = 2^16 조합이 나올 수 있다.

 

재귀로 돌면서 각 조합을 확인해준다.

재귀로 들어가며 각 CCTV 특성에 맞게 check 배열에 CCTV로 확인 가능한 부분을 표시해주고,

끝까지 내려갔을 때(depth == CCTV 개수), map, check가 둘다 0인 곳 개수 카운팅, minimum이면 갱신해준다.

#define MAX 9
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

struct CCTV{
    int num;
    int x;
    int y;
};
int N, M;
int map[MAX][MAX];
int check[MAX][MAX];
vector<CCTV> cctvs; // save cctv nums
int minBlind = 987654321;
int rotateN[5] = {4, 2, 4, 4, 1};


void mapcpy(int desc[MAX][MAX], int src[MAX][MAX])
{
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < M; ++c)
            desc[r][c] = src[r][c];
}

void checking(int cNum, int dir){
    
    dir %= 4;
    if(dir==0){ // north
        for(int i=cctvs[cNum].x; i>=0; i--){
            if(map[i][cctvs[cNum].y] == 6){
                break;
            }
            check[i][cctvs[cNum].y] = cctvs[cNum].num;
        }
    }
    else if(dir==1){ //east
        for(int i=cctvs[cNum].y; i<M; i++){
            if(map[cctvs[cNum].x][i] == 6){
                break;
            }
            check[cctvs[cNum].x][i] = cctvs[cNum].num;
        }    
    }
    else if(dir==2){ //south
       for(int i=cctvs[cNum].x; i<N; i++){
            if(map[i][cctvs[cNum].y] == 6){
                break;
            }
            check[i][cctvs[cNum].y] = cctvs[cNum].num;
        }     
    }
    else{ //west
        for(int i=cctvs[cNum].y; i>=0; i--){
            if(map[cctvs[cNum].x][i] == 6){
                break;
            }
            check[cctvs[cNum].x][i] = cctvs[cNum].num;
        }    
    }
    
    return;
}


void bf(int depth){
    
    //base case
    if(depth == cctvs.size()){
        int zero_num = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j]==0 && check[i][j]==0){
                    zero_num++;
                }
            }
        }
        
        minBlind = min(minBlind, zero_num);
        return;
    }
    
    int temp[MAX][MAX];
    int toCheck = cctvs[depth].num;
    
    for(int dir=0; dir<rotateN[toCheck-1]; dir++){
        
        mapcpy(temp, check);
        
        //check에 표시
        if(toCheck==1){ 
            checking(depth, dir);
        }
        else if(toCheck==2){ 
            checking(depth, dir);
            checking(depth, dir+2);
        }
        else if(toCheck==3){
            checking(depth, dir);
            checking(depth, dir+1);
        }
        else if(toCheck==4){
            checking(depth, dir);
            checking(depth, dir+1);
            checking(depth, dir+2);
        }
        else{
            checking(depth, dir);
            checking(depth, dir+1);
            checking(depth, dir+2);
            checking(depth, dir+3);
        }
        
        //next call
        bf(depth+1);
        
        mapcpy(check, temp);
    }
}

void initialize(){
    
    cin>>N>>M;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>map[i][j];
            if(map[i][j]>0 && map[i][j]<6){
                cctvs.push_back({map[i][j], i, j});
            }
        }
    }
}

int main()
{
    initialize();

    bf(0);
    
    cout<<minBlind<<"\n";

    return 0;
}

wow

푸는데 진짜 오래걸렸다.

생각보다 구현이 복잡하다ㅜㅜㅜㅜ

어디서 각 방향 체크해주고

어디서 CCTV 별로 rotation 시켜주고

어디서 재귀콜을 할지

정하는게 너무 어려웠다ㅜㅜ

마지막에 checking 함수에서 dir%=4 안해줘서 틀렸다.

 

-> 질문 게시판글의 예시들을 돌려보다

5 5
0 0 0 0 0
6 2 0 0 4
0 0 0 4 0
5 0 0 5 0
6 0 0 0 0
correct = 3, wrong = 5

->4가 나옴 ㅋ

얘가 안되서 열심히 고민해보니, cctv num=4일때 dir이 4를 넘어가서 생긴 문제였다ㅜㅜ