[구현]백준15683번 감시

백준15683

처음에 단순 구현이나 시뮬레이션으로 해결하려고 했는데 너무 코드가 복잡하고 결과적으로는 로직에 문제가 생겨서 풀이를 찾아보게 되었다.

풀이는 dfs를 사용했다.

dfs를 사용하기 전에 준비해야 할 것이 몇 가지 있다.

우선 cctv의 정보를 저장할 자료구조는 tuple을 사용했다.

tuple을 통해 cctv의 <y, x, type> 를 저장하도록 하였다.

각 CCTV는 한 번에 감시할 수 있는 방향이 정해져있고, 그에 따라 돌아갈 수 있는 가짓수가 각각 다르다.

따라서 카메라 별로 가능한 가짓수를 배열에 미리 담아두어야 한다.

카메라가 하나의 방향을 감시할 때의 모든 경우의 수를 탐색해야 하기 때문에, 전체 지도를 백업하고 다음 cctv를 돌릴 수 있도록 dfs 함수를 타고 들어가야 한다.

dfs 함수의 기저 조건은 주어진 cctv들을 모두 조합했을 때, 즉 카메라들이 담겨있는 벡터의 사이즈만큼 dfs 함수를 타고 들어갔을 때 0의 개수를 확인하는 것이다.

미리 만들어놨던 cctv 타입 별 회전 가짓수 배열을 이용해 for문을 돌리기 때문에 각 cctv마다 모든 조합을 확인해볼 수 있다.

돌아가는 방향은 오른쪽이 0, 윗 쪽이 1, 왼쪽이 2, 아랫쪽이 3으로 두면 매개변수로 어떤 방향을 확인할지 넘겨줄 수 있다.

특정 방향으로 카메라를 돌렸을 때의 경우의 수를 확인할 때는 별도의 함수를 만들어 수행했는데, 해당 방향으로 6이 나오거나 끝에 도달할 때까지 표시하는 함수를 만들었다.

void update(int dir,int cctv_index){
    dir = dir % 4;
    int y = get<0>(t[cctv_index]);
    int x = get<1>(t[cctv_index]);
    
    // East
    if(dir == 0){
        for(int i=x+1;i<M;i++){
            if(office[y][i] != 6){
                office[y][i] = -1;
            }
            else break;
        }
    }
    if(dir == 1) {
        for(int i=y-1;i>=0;i--){
            if(office[i][x] != 6){
                office[i][x] = -1;
            }
            else break;
        }
    }
    if(dir == 2) {
        for(int i=x-1;i>=0;i--){
            if(office[y][i] != 6){
                office[y][i] = -1;
            }
            else break;
        }
    }
    if(dir == 3) {
        for(int i=y+1;i<N;i++){
            if(office[i][x]!=6){
                office[i][x] = -1;
            }
            else break;
        }
    }
}

dfs 함수에서는 이 update 함수에 방향을 나타내는 매개변수를 각각 다르게 주고, 각각 다르게 조합하여 사용할 수 있다.

void dfs(int cctv_index){
    if(cctv_index == t.size()){
        // check area
        int cnt = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(office[i][j] == 0) cnt++;
            }
        }
        if(answer >= cnt) answer = cnt;
        return;
    }
    int backup[8][8];
    int type= get<2>(t[cctv_index]);
    for(int dir = 0; dir < sizeDir[type];dir++){
        // save office
        mapCopy(backup, office);
        if(type ==0){
            update(dir,cctv_index);
        }
        else if (type == 1) {
            update(dir,cctv_index);
            update(dir+2,cctv_index);
        }
        else if (type == 2) {
            update(dir,cctv_index);
            update(dir+1,cctv_index);
        }
        else if (type == 3) {
            update(dir,cctv_index);
            update(dir+1,cctv_index);
            update(dir+2,cctv_index);
        }
        else if (type == 4) {
            update(dir,cctv_index);
            update(dir+1,cctv_index);
            update(dir+2,cctv_index);
            update(dir+3,cctv_index);
        }
        dfs(cctv_index + 1);
        // restore office
        mapCopy(office, backup);
    }
}

전체 코드는 다음과 같다.

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

int N,M;
int office[8][8];
vector<tuple<int,int,int> > t;
const int sizeDir[] = {4,2,4,4,1};
int answer;

void mapCopy(int dst[8][8], int src[8][8]){
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            dst[i][j] = src[i][j];
        }
    }
}

void update(int dir,int cctv_index){
    dir = dir % 4;
    int y = get<0>(t[cctv_index]);
    int x = get<1>(t[cctv_index]);
    
    // East
    if(dir == 0){
        for(int i=x+1;i<M;i++){
            if(office[y][i] != 6){
                office[y][i] = -1;
            }
            else break;
        }
    }
    if(dir == 1) {
        for(int i=y-1;i>=0;i--){
            if(office[i][x] != 6){
                office[i][x] = -1;
            }
            else break;
        }
    }
    if(dir == 2) {
        for(int i=x-1;i>=0;i--){
            if(office[y][i] != 6){
                office[y][i] = -1;
            }
            else break;
        }
    }
    if(dir == 3) {
        for(int i=y+1;i<N;i++){
            if(office[i][x]!=6){
                office[i][x] = -1;
            }
            else break;
        }
    }
}

void dfs(int cctv_index){
    if(cctv_index == t.size()){
        // check area
        int cnt = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
//                cout << office[i][j] << " ";
                if(office[i][j] == 0) cnt++;
            }
//            cout << endl;
        }
        if(answer >= cnt) answer = cnt;
        return;
    }
    int backup[8][8];
    int type= get<2>(t[cctv_index]);
    for(int dir = 0; dir < sizeDir[type];dir++){
        // save office
        mapCopy(backup, office);
        if(type ==0){
            update(dir,cctv_index);
        }
        else if (type == 1) {
            update(dir,cctv_index);
            update(dir+2,cctv_index);
        }
        else if (type == 2) {
            update(dir,cctv_index);
            update(dir+1,cctv_index);
        }
        else if (type == 3) {
            update(dir,cctv_index);
            update(dir+1,cctv_index);
            update(dir+2,cctv_index);
        }
        else if (type == 4) {
            update(dir,cctv_index);
            update(dir+1,cctv_index);
            update(dir+2,cctv_index);
            update(dir+3,cctv_index);
        }
        dfs(cctv_index + 1);
        // restore office
        mapCopy(office, backup);
    }
}

int main(){
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> office[i][j];
            if(office[i][j] >0 && office[i][j]<6) t.push_back(make_tuple(i,j,office[i][j]-1));
        }
    }
    answer = 99;
    dfs(0);
    
    cout << answer;
    
}