백준 알고리즘 15683

입력 : 사무실 사이즈와 cctv, 벽의 위치

출력 : cctv의 사각지대를 최소화했을 때의 사각지대의 수

 

풀이

1. cctv는 총 4개의 방향으로 회전시킬 수 있다. 때문에 카메라가 N개라면 만들 수 있는 상황의 수는 4^N이다.

2. 카메라 종류에 따라 확인할 수 있는 방향을 미리 저장해둔다.

3. 4^N개의 상황에 카메라의 위치와 카메라가 보고있는 방향을 벡터변수에 넣는다.

4. 마지막에 0의 갯수를 확인하며 가장 적은 경우를 리턴한다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct Point{
	int x;
	int y;
};

Point getPoint(int x, int y){
	Point result;
	result.x = x;
	result.y = y;
	
	return result;
}

int direction[4][2] = {{0,-1}, {1,0}, {0,1}, {-1,0}};

int board[10][10];
int boardCopy[10][10];
vector<Point> camera;

vector<vector<int> > camDirect = {{}, {0}, {0,2}, {0,1}, {0,1,2}, {0,1,2,3}};
vector<int> camDirectStatus;
vector<Point> camPositionStatus;
int N,M;

void checkCamera(Point pos, int Direct){
	for(int i=1; true; i++){
		Point p = getPoint(pos.x + direction[Direct][0] * i, pos.y + direction[Direct][1] * i);
		if(p.x >= N || p.x < 0 || p.y >= M || p.y < 0 || boardCopy[p.x][p.y] == 6)
			break;
		
		boardCopy[p.x][p.y] = -1;
	}
}

int getZero(){
	int result = 0;
	
	for(int i=0; i<N; i++)
		memcpy(boardCopy[i], board[i], sizeof(int)*M);
	
	for(int i=0; i<camDirectStatus.size(); i++)
		checkCamera(camPositionStatus[i], camDirectStatus[i]);
	
	for(int i=0; i<N; i++)
		for(int j=0; j<M; j++)
			if(boardCopy[i][j] == 0)
				result++;

	return result;
}

int checkCamera(int n){
	if(n == camera.size())
		return getZero();
	
	Point camPos = camera[n];
	int camType = board[camPos.x][camPos.y];
	int min = 1000;
	
	for(int i=0; i<4; i++){
		int lenseSize = camDirect[camType].size();
		
		for(int j=0; j<lenseSize; j++){
			camPositionStatus.push_back(camPos);
			camDirectStatus.push_back((camDirect[camType][j] + i) % 4);
		}
		
		int result = checkCamera(n+1);
		
		if(result < min)
			min = result;
			
		for(int j=0; j<lenseSize; j++){
			camPositionStatus.pop_back();
			camDirectStatus.pop_back();
		}
	}
	
	return min;
}

int main() {
	cin>>N>>M;
	initCamDirect();
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			cin>>board[i][j];
			
			if(board[i][j] == 0)
				continue;
			else if(board[i][j] < 6)
				camera.push_back(getPoint(i, j));
		}
	}
	
	cout<<checkCamera(0)<<endl;
	
	return 0;
}