[BOJ] 백준 15683 감시 c++ 코드 / 풀이

https://www.acmicpc.net/problem/15683

15683번: 감시

 

 

문제해설

 

문제에 상당히 설명히 상세하게 되어있어서 아마 문제 자체를 이해하는 건 어렵지 않다고 생각함

최대 8x8 칸의 사무실이 있을 때 최대 8대의 cctv가 랜덤한 공간에 있고 각 cctv는 5가지의 형태가 존재함

이때 각 칸의 값이 0이면 빈칸, 1~5면 cctv 6이면 벽이라고 할 때 감시 할 수 없는 칸(사각지대)의 최소값을 구하면 됨

대신 귀찮아지는게 cctv 1~4는 90도씩 회전이 가능하므로 이를 고려해서 풀어야됨

 

문제풀이

 

좌표의 형식으로 cctv의 위치를 별도로 저장해놓고상하좌우로 나가면서 벽이나 배열 범위를 초과할 때 까지감시가 가능한 공간을 체크

단 회전을 하면서 감시 범위를 최대화 해야되므로 입력 배열을 복사해서 실제로 -을 -1(#)으로 변경해가면서 체크

위 과정을 모든 cctv에 적용시키면서 90도씩 돌려가며 4번 반복하여 해결

 

코드설명

 

입력을 받으면서 cctv의 위치를 저장

1번은 한방향, 2번은 두 방향, 3번은 수직 두방향 이런식으로 1~5번 cctv의 방향을 설정

DFS 탐색으로 가능한 모든 조합을 시도하며 최대 감시 범위 탐색

감시 가능한 영역을 표시하며 진행하고, 초기 사무실 상태를 유지하기 위해 복사하여 진행

(코드의 길이가 길뿐 복잡하진 않으니 천천히 보면 이해가 어렵진....않을듯..?)

 

코드

#include <bits/stdc++.h>

using namespace std;

/*
    pair로 cctv의 위치 저장, vector size로 cctv개수 산정 가능
    상하좌우좌표를 세팅
    x,y,dir를 입력받아 방문체크(#=-1)하는 함수 생성하여 체크 
    이후 재귀로 백트래킹
    base condition은 현재 방문체크한 cctv의 개수가 전체 cctv의 개수와 같을때
    이때 리턴해주면서 사각지대의 최소개수 체크
    내부 코드는 복사된 맵을 기반으로 dir을 (0~4)의 범위를 적용(4개의 방향회전을 위해)
    복사된 맵을 순회하면서 해당 값이 1~5면 dir를 인덱스로 방문체크 함수 실행
    1이면 한번 2번 양쪽 두번, 3이면 90도 두번, 4면 3방향, 5면 모든 방향이 돌도록
    이후 cctv의 개수++ 하여 재귀 
*/

int N, M, num, cnt=65;
int dx[4] = {1, 0 , -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> arr;
vector<vector<int>> copyArr;//복사본
vector<pair<int, int>> v;// 각 cctv의 좌표, 1번 cctv가 0,1에 있을 경우 v[1]에 (0,1)이 삽입됨

//dir(0=아래, 1=오른쪽, 2=위쪽, 3=왼쪽)
void bfs(int x, int y, int dir){
    dir %= 4;
    
    while(1){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        x = nx;
        y = ny;//한 방향으로 나아가면서 체크하도록 증가
        if(nx < 0 || nx >= N || ny < 0 || ny >= M) return;
        if(arr[nx][ny] == 6) return;
        if(arr[nx][ny] != 0) continue;
        arr[nx][ny] = -1; //#
    }
}

void calc(int cctvCount){
    if(cctvCount == v.size()){
        int sum = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] == 0) sum++;
            }
        }
        cnt = min(sum, cnt);
        return;
    }
    int x = v[cctvCount].first;
    int y = v[cctvCount].second;
    vector<vector<int>> copyArr = arr;
    for(int i = 0; i < 4; i++){
        copyArr = arr;//현재까지의 진행단계 반영
        if(arr[x][y] == 1){
            bfs(x,y,i);
        }
        else if(arr[x][y] == 2){//양쪽 두방향
            bfs(x,y,i);
            bfs(x,y,i+2);
        }
        else if(arr[x][y] == 3){//수직 두방향
            bfs(x,y,i);
            bfs(x,y,i+1);
        }
        else if(arr[x][y] == 4){
            bfs(x,y,i);
            bfs(x,y,i+1);
            bfs(x,y,i+2);
        }
        else if(arr[x][y] == 5){
            bfs(x,y,i);
            bfs(x,y,i+1);
            bfs(x,y,i+2);
            bfs(x,y,i+3);
        }
        calc(cctvCount + 1);
        arr = copyArr;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;

    for(int i = 0; i < N; i++){
        vector<int> tmp;
        for(int j = 0; j < M; j++){
            cin >> num;
            tmp.push_back(num);
            if(num >= 1 && num <= 5){
                v.push_back({i,j});
            }
        }
        arr.push_back(tmp);
    }
    calc(0);
    cout << cnt;

}