(C++) 백준 15683번 - 감시

문제 링크 : https://www.acmicpc.net/problem/15683

15683번: 감시

풀이

백트래킹을 사용하여 풀이하였다.

먼저 전체 사무실에서 CCTV가 위치한 곳의 좌표를 Queue에 넣는다.

다음으로 Queue의 Front에 위치한 CCTV가 스캔할 수 있는 지역을 체크한다.

체크한 뒤 사무실의 정보와 Queue를 함수의 변수로 넘겨가면서 Queue가 빌 때까지 재귀적으로 진행한다. 

#include <iostream>
#include <queue>
#include <algorithm>
#define X first
#define Y second

using namespace std;

int n, m;
int brd[10][10];
int ans = 100;
int dx[4] = {1, 0, -1, 0}; // CCTV가 바라보는 방향 저장
int dy[4] = {0, 1, 0, -1}; // CCTV가 바라보는 방향 저장
queue<pair<int,int> > Q;

void calbspot(int brd[10][10], queue<pair<int,int> > Q){
    if(Q.empty()){
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(brd[i][j] == 0) cnt++;    
            }
        }
        ans = min(cnt, ans);
        return;
    }
    auto k = Q.front();
    int cx = k.X;
    int cy = k.Y;
    Q.pop();
    if(brd[cx][cy] == 1){ // 1번 CCTV
        for(int i = 0; i < 4; i++){
            int tmp[10][10]; // 수정이 진행되는 brd이기 때문에 복사할 배열 선언
            copy(&brd[0][0], &brd[0][0] + 100, &tmp[0][0]); // 복사 진행
            int tmpx = cx; // 마찬가지로 수정이 진행되므로 원래 값 복사
            int tmpy = cy; // 마찬가지로 수정이 진행되므로 원래 값 복사
            while(1){
                tmpx += dx[i]; // 다음 위치
                tmpy += dy[i]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            calbspot(tmp, Q);
        }
    }
    if(brd[cx][cy] == 2){ // 2번 CCTV
        for(int i = 0; i < 2; i++){
            int tmp[10][10]; // brd는 수정되기 때문에 복사할 배열(tmp) 선언
            copy(&brd[0][0], &brd[0][0] + 100, &tmp[0][0]); // 복사 진행
            int tmpx = cx; // 마찬가지로 수정되므로 원래 값 복사
            int tmpy = cy; // 마찬가지로 수정되므로 원래 값 복사
            while(1){
                tmpx += dx[i]; // 다음 위치
                tmpy += dy[i]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            tmpx = cx; // 다시 시작 위치로
            tmpy = cy; // 다시 시작 위치로
            while(1){
                tmpx += dx[i+2]; // 다음 위치
                tmpy += dy[i+2]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            calbspot(tmp, Q);
        }
    }
    if(brd[cx][cy] == 3){ // 3번 CCTV
        for(int i = 0; i < 4; i++){
            int tmp[10][10]; // brd는 수정되기 때문에 복사할 배열(tmp) 선언
            copy(&brd[0][0], &brd[0][0] + 100, &tmp[0][0]); // 복사 진행
            int tmpx = cx; // 마찬가지로 수정되므로 원래 값 복사
            int tmpy = cy; // 마찬가지로 수정되므로 원래 값 복사
            while(1){
                tmpx += dx[i]; // 다음 위치
                tmpy += dy[i]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            tmpx = cx; // 다시 시작 위치로
            tmpy = cy; // 다시 시작 위치로
            while(1){
                tmpx += dx[(i+1)%4]; // 다음 위치
                tmpy += dy[(i+1)%4]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            calbspot(tmp, Q);
        }
    }
    if(brd[cx][cy] == 4){ // 4번 CCTV
        for(int i = 0; i < 4; i++){
            int tmp[10][10]; // brd는 수정되기 때문에 복사할 배열(tmp) 선언
            copy(&brd[0][0], &brd[0][0] + 100, &tmp[0][0]); // 복사 진행
            int tmpx = cx; // 마찬가지로 수정되므로 원래 값 복사
            int tmpy = cy; // 마찬가지로 수정되므로 원래 값 복사
            while(1){
                tmpx += dx[i]; // 다음 위치
                tmpy += dy[i]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            tmpx = cx; // 다시 시작 위치로
            tmpy = cy; // 다시 시작 위치로
            while(1){
                tmpx += dx[(i+1)%4]; // 다음 위치
                tmpy += dy[(i+1)%4]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            tmpx = cx; // 다시 시작 위치로
            tmpy = cy; // 다시 시작 위치로
            while(1){
                tmpx += dx[(i+2)%4]; // 다음 위치
                tmpy += dy[(i+2)%4]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
            calbspot(tmp, Q);
        }
    }
    if(brd[cx][cy] == 5){ // 5번 CCTV
        int tmp[10][10]; // brd는 수정되기 때문에 복사할 배열(tmp) 선언
        copy(&brd[0][0], &brd[0][0] + 100, &tmp[0][0]); // 복사 진행
        for(int i = 0; i < 4; i++){
            int tmpx = cx; // 마찬가지로 수정되므로 원래 값 복사
            int tmpy = cy; // 마찬가지로 수정되므로 원래 값 복사
            while(1){
                tmpx += dx[i]; // 다음 위치
                tmpy += dy[i]; // 다음 위치
                if(tmpx < 0 or tmpx >= n or tmpy < 0 or tmpy >= m) break; // 유효성 검사
                if(brd[tmpx][tmpy] == 6) break; // 벽과 만나면 CCTV는 더 나아갈 수 없음
                if(brd[tmpx][tmpy] == 0) tmp[tmpx][tmpy] = -1; // 해당 칸들은 CCTV가 스캔을 하는 곳들
            }
        }
        calbspot(tmp, Q);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> brd[i][j]; // 사무실 정보 입력
            if(brd[i][j] == 0 or brd[i][j] == 6) continue; 
            Q.emplace(i, j); // CCTV 정보를 큐에 입력
        }
    }
    calbspot(brd, Q);
    cout << ans;
}