• 문제풀이/백준oj

    [백준OJ] 15683번 감시

    2021. 4. 26.

    by. Hyeon-Uk

    반응형

     

    www.acmicpc.net/problem/15683

     

    15683번: 감시

    스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

    www.acmicpc.net

     

    -풀이-

    입력받을 때, cctv들은 모두 벡터에 넣어둔 뒤, 백트래킹을 이용하여 , 모든 cctv들이 감시할 수 있는 상황을 구해주고, 최소 사각지대를 업데이트 해준다.

    이때 아래 함수들로 인해, 입력받은 배열들을 모두 음수로 바꿔준다.

     

     

    paint함수: 원하는 방향에 따라 감시카메라기준 해당방향으로 표시를 해준다. 이때 백트래킹을 할때 다른 cctv로인해 지워지지 않게, 현재 cctv인덱스+1로 표시 해준다.

    void paint(int x,int y,int d,int cnt){
    if(d==0){
        for(int i=x-1;i>=0;i--){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==0) maze[i][y]=cnt+1;
        }
    }
    else if(d==1){
        for(int i=y+1;i<m;i++){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==0) maze[x][i]=cnt+1;
        }
    }
    else if(d==2){
        for(int i=x+1;i<n;i++){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==0) maze[i][y]=cnt+1;
        }
    }
    else{
        for(int i=y-1;i>=0;i--){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==0) maze[x][i]=cnt+1;
        }
    }
}

     

    remove_paint함수:

    백트래킹을 할때, 해당 cctv가 볼 수 있는 범위라고 표시한것만 지워주는 함수이다.

    void remove_paint(int x,int y,int d,int cnt){
    if(d==0){
        for(int i=x-1;i>=0;i--){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==cnt+1) maze[i][y]=0;
        }
    }
    else if(d==1){
        for(int i=y+1;i<m;i++){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==cnt+1) maze[x][i]=0;
        }
    }
    else if(d==2){
        for(int i=x+1;i<n;i++){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==cnt+1) maze[i][y]=0;
        }
    }
    else{
        for(int i=y-1;i>=0;i--){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==cnt+1) maze[x][i]=0;
        }
    }
}

     

    dfs함수:

    모든 경우의수를 만들어주는 백트래킹 함수. 각각의 경우의수마다 사각지대의 개수를 카운팅하여 업데이트 해준다.

    void dfs(int now){
    if(now==cctv.size()){
        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(maze[i][j]==0) cnt++;
            }
        }        
        result=min(result,cnt);
        return;
    }
    int number=cctv[now].second;
    int x=cctv[now].first.first;
    int y=cctv[now].first.second;
    if(number==1){
        for(int i=0;i<4;i++){
            paint(x,y,i,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
        }
    }
    else if(number==2){
        for(int i=0;i<2;i++){
            paint(x,y,i,now);
            paint(x,y,i+2,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
            remove_paint(x,y,i+2,now);
        }
    }
    else if(number==3){
        paint(x,y,0,now);
        for(int i=0;i<4;i++){
            paint(x,y,(i+1)%4,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
        }
        remove_paint(x,y,0,now);
        
    }
    else if(number==4){
        paint(x,y,0,now);
        paint(x,y,1,now);
        
        for(int i=0;i<4;i++){
            paint(x,y,(i+2)%4,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
        }
        
        remove_paint(x,y,0,now);
        remove_paint(x,y,1,now);
    }
    else{
        for(int i=0;i<4;i++){
            paint(x,y,i,now);
        }
        dfs(now+1);
        for(int i=0;i<4;i++){
            remove_paint(x,y,i,now);
        }
    }
}

     

    -시간복잡도-

    cctv하나가 최대 4가지의 경우가 나오므로, 최악의 경우는 총 O(4^K) , K는 cctv개수가 된다. 하지만 K<=8이므로 시간안에 충분히 들어온다.

     

    -코드-

     

    #include<iostream>
#include<algorithm>
using namespace std;

int maze[8][8];
int n,m,result=64;
vector<pair<pair<int,int>,int>> cctv;
//d=0 위, d=1 오,d=2 아, d=3 왼
void paint(int x,int y,int d,int cnt){
    if(d==0){
        for(int i=x-1;i>=0;i--){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==0) maze[i][y]=cnt+1;
        }
    }
    else if(d==1){
        for(int i=y+1;i<m;i++){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==0) maze[x][i]=cnt+1;
        }
    }
    else if(d==2){
        for(int i=x+1;i<n;i++){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==0) maze[i][y]=cnt+1;
        }
    }
    else{
        for(int i=y-1;i>=0;i--){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==0) maze[x][i]=cnt+1;
        }
    }
}

void remove_paint(int x,int y,int d,int cnt){
    if(d==0){
        for(int i=x-1;i>=0;i--){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==cnt+1) maze[i][y]=0;
        }
    }
    else if(d==1){
        for(int i=y+1;i<m;i++){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==cnt+1) maze[x][i]=0;
        }
    }
    else if(d==2){
        for(int i=x+1;i<n;i++){
            if(maze[i][y]==-6) break;
            if(maze[i][y]==cnt+1) maze[i][y]=0;
        }
    }
    else{
        for(int i=y-1;i>=0;i--){
            if(maze[x][i]==-6) break;
            if(maze[x][i]==cnt+1) maze[x][i]=0;
        }
    }
}

void dfs(int now){
    if(now==cctv.size()){
        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(maze[i][j]==0) cnt++;
            }
        }        
        result=min(result,cnt);
        return;
    }
    int number=cctv[now].second;
    int x=cctv[now].first.first;
    int y=cctv[now].first.second;
    if(number==1){
        for(int i=0;i<4;i++){
            paint(x,y,i,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
        }
    }
    else if(number==2){
        for(int i=0;i<2;i++){
            paint(x,y,i,now);
            paint(x,y,i+2,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
            remove_paint(x,y,i+2,now);
        }
    }
    else if(number==3){
        paint(x,y,0,now);
        for(int i=0;i<4;i++){
            paint(x,y,(i+1)%4,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
        }
        remove_paint(x,y,0,now);
        
    }
    else if(number==4){
        paint(x,y,0,now);
        paint(x,y,1,now);
        
        for(int i=0;i<4;i++){
            paint(x,y,(i+2)%4,now);
            dfs(now+1);
            remove_paint(x,y,i,now);
        }
        
        remove_paint(x,y,0,now);
        remove_paint(x,y,1,now);
    }
    else{
        for(int i=0;i<4;i++){
            paint(x,y,i,now);
        }
        dfs(now+1);
        for(int i=0;i<4;i++){
            remove_paint(x,y,i,now);
        }
    }
}

int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>maze[i][j];
            if(maze[i][j]!=0&&maze[i][j]!=6){
                cctv.push_back({{i,j},maze[i][j]});
                maze[i][j]=-maze[i][j];
            }
            else if(maze[i][j]==6){
                maze[i][j]=-6;
            }
        }
    }
    
    dfs(0);

    cout<<result<<"\n";
    return 0;
}
    반응형
    저작자표시

    '문제풀이 > 백준oj' 카테고리의 다른 글

    [백준OJ] 15686번 치킨 배달  (0) 2021.04.27
    [백준OJ] 15685번 드래곤 커브  (0) 2021.04.27
    [백준OJ] 14891번 톱니바퀴  (0) 2021.04.26
    [백준OJ] 14890번 경사로  (0) 2021.04.25
    [백준OJ] 14889번 스타트와 링크  (0) 2021.04.25

    댓글

    관련글

    맨 위로
전체 글 보기

티스토리툴바