(백준 c++)15683 감시

www.acmicpc.net/problem/15683

15683번: 감시

 

브루트포스로 진행.

 

N * M 영역의 정보를 저장.

카메라가 있는 좌표는 v 벡터에 저장한다.

그 후 dfs로 모든 사각지대를 파악한다.

 

만약 v가 비어있다면 카메라가 없다는 뜻이다.

그러면 cameraCheck() 함수를 통해 0의 개수를 구하도록 한다.

 

v가 비어있지 않다면 카메라를 회전시켜서 사각지대의 최소 크기를 구하도록 한다.

공통적으로 상하좌우의 방향을 검사하기 때문에 함수를 각각 만들어준다.

 

그리고 카메라 번호에 맞게 카메라를 감시 영역을 -1로 표시하여 dfs를 진행한다.

특이점은 한 카메라의 방향마다 감시 영역이 달라지기 때문에 board를 복사하여 dfs 함수에 넘겨주어야 한다.

#include <iostream>
#include <vector>

using namespace std;

int N = 0;
int M = 0;
int ans = 0;
vector<pair<int, int>> v;

vector<vector<int>> upCheck(int x, int y, vector<vector<int>> board){
    for(int i = x - 1; i >= 0; i--){
        if(board[i][y] == 6){
            return board;
        }
        else if(board[i][y] == 0){
            board[i][y] = -1;
        }
    }
    return board;
}

vector<vector<int>> downCheck(int x, int y, vector<vector<int>> board){
    for(int i = x + 1; i < N; i++){
        if(board[i][y] == 6){
            return board;
        }
        else if(board[i][y] == 0){
            board[i][y] = -1;
        }
    }
    return board;
}

vector<vector<int>> leftCheck(int x, int y, vector<vector<int>> board){
    for(int i = y - 1; i >= 0; i--){
        if(board[x][i] == 6){
            return board;
        }
        else if(board[x][i] == 0){
            board[x][i] = -1;
        }
    }
    return board;
}

vector<vector<int>> rightCheck(int x, int y, vector<vector<int>> board){
    for(int i = y + 1; i < M; i++){
        if(board[x][i] == 6){
            return board;
        }
        else if(board[x][i] == 0){
            board[x][i] = -1;
        }
    }
    return board;
}

void cameraCheck(vector<vector<int>> board){
    int sum = 0;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(board[i][j] == 0){
                sum++;
            }
        }
    }

    ans = ans > sum ? sum : ans;
}

void dfs(int index, vector<vector<int>> board){
    if(index == v.size()){
        cameraCheck(board);
        return;
    }

    int x = v[index].first;
    int y = v[index].second;
    vector<vector<int>> tmpBoard;   

    switch(board[x][y]){
        case 1:
            tmpBoard = upCheck(x, y, board);
            dfs(index + 1, tmpBoard);

            tmpBoard = downCheck(x, y, board);
            dfs(index + 1, tmpBoard);

            tmpBoard = leftCheck(x, y, board);
            dfs(index + 1, tmpBoard);

            tmpBoard = rightCheck(x, y, board);
            dfs(index + 1, tmpBoard);
            break;

        case 2:
            tmpBoard = rightCheck(x, y, board);
            tmpBoard = leftCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = upCheck(x, y, board);
            tmpBoard = downCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);
            break;

        case 3:
            tmpBoard = upCheck(x, y, board);
            tmpBoard = rightCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = rightCheck(x, y, board);
            tmpBoard = downCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = downCheck(x, y, board);
            tmpBoard = leftCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = leftCheck(x, y, board);
            tmpBoard = upCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);
            break;

        case 4:
            tmpBoard = leftCheck(x, y, board);
            tmpBoard = upCheck(x, y, tmpBoard);
            tmpBoard = rightCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = upCheck(x, y, board);
            tmpBoard = rightCheck(x, y, tmpBoard);
            tmpBoard = downCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = rightCheck(x, y, board);
            tmpBoard = downCheck(x, y, tmpBoard);
            tmpBoard = leftCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);

            tmpBoard = downCheck(x, y, board);
            tmpBoard = leftCheck(x, y, tmpBoard);
            tmpBoard = upCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);
            break;

        case 5:
            tmpBoard = upCheck(x, y, board);
            tmpBoard = downCheck(x, y, tmpBoard);
            tmpBoard = leftCheck(x, y, tmpBoard);
            tmpBoard = rightCheck(x, y, tmpBoard);
            dfs(index + 1, tmpBoard);
            break;
    }
}

int main(void){
    vector<vector<int>> board(8, vector<int>(8, 0));

    cin >> N >> M;

    ans = N * M;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> board[i][j];

            //cctv 위치 v 벡터에 삽입
            if(board[i][j] >= 1 && board[i][j] <= 5){
                v.push_back({i, j});
            }
        }
    }

	if(!v.empty()){
    	dfs(0, board);
	}
    else{
        cameraCheck(board);
    }

    cout << ans;

    return 0;
}