[백준/BOJ] 백준 15683번 : 감시

www.acmicpc.net/problem/15683

15683번: 감시

int cctv_dir[6][4][4]를 통해 각 cctv(1~5)의 번호마다, 바라보는 방향에 따라, 감시 가능한 방향을 표시한다. 각 cctv 방향의 경우들을 모두 확인하여 사각지대 크기의 최솟값을 구한다.

 

코드

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

int n, m;
int board[8][8];
int temp_board[8][8];
int cctv_dir[6][4][4] = { //각cctv(1~5)의 번호 마다, 바라보는 방향에 따라, 감시 가능한 방향을 표시한다
	{{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},
	{{0,0,1,0},{0,0,0,1},{1,0,0,0},{0,1,0,0}},
	{{1,0,1,0},{0,1,0,1},{1,0,1,0},{0,1,0,1}},
	{{0,1,1,0},{0,0,1,1},{1,0,0,1},{1,1,0,0}},
	{{1,1,1,0},{0,1,1,1},{1,0,1,1},{1,1,0,1}},
	{{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}}
};
vector<pair<int, pair<int, int>>> cctv;
int result = 987654321;

//배열을 복사한다
void boardCopy(int to[][8], int from[][8])
{
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
		{
			to[i][j] = from[i][j];
		}
}

//각 cctv의 방향이 모두 정해졌을때 사각지대의 개수를 구한다
int Check(vector<int>& select)
{
	int ret = 0;

	for (int i = 0; i < cctv.size(); i++)
	{
		int this_cctv_kind = cctv[i].first; //cctv의 종류 
		int this_cctv_dir = select[i]; //cctv의 방향
		pair<int, int> this_cctv_xy = cctv[i].second; //cctv의 위치

		//4방향을 확인해 본다
		for (int j = 0; j < 4; j++)
		{
			//해당 방향을 cctv가 감시할 수 있을때
			//감시 가능한 칸을 -1로 표시
			if (cctv_dir[this_cctv_kind][this_cctv_dir][j] == 1)
			{
				if (j == 0)
				{
					for (int k = this_cctv_xy.second - 1; k >= 0; k--)
					{
						if (board[this_cctv_xy.first][k] == 6)
							break;
						if (board[this_cctv_xy.first][k] == 0)
							board[this_cctv_xy.first][k] = -1;
					}
				}

				if (j == 1)
				{
					for (int k = this_cctv_xy.first - 1; k >= 0; k--)
					{
						if (board[k][this_cctv_xy.second] == 6)
							break;
						if (board[k][this_cctv_xy.second] == 0)
							board[k][this_cctv_xy.second] = -1;
					}
				}

				if (j == 2)
				{
					for (int k = this_cctv_xy.second + 1; k < m; k++)
					{
						if (board[this_cctv_xy.first][k] == 6)
							break;
						if (board[this_cctv_xy.first][k] == 0)
							board[this_cctv_xy.first][k] = -1;
					}
				}

				if (j == 3)
				{
					for (int k = this_cctv_xy.first + 1; k < n; k++)
					{
						if (board[k][this_cctv_xy.second] == 6)
							break;
						if (board[k][this_cctv_xy.second] == 0)
							board[k][this_cctv_xy.second] = -1;
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			//사각지대의 크기를 구한다
			if (board[i][j] == 0)
				ret++;
		}

	//다음을 위해 다시 원본으로 바꾼다
	boardCopy(board, temp_board);

	return ret;
}

int Solve(vector<int>& select)
{
	int ret = 987654321;

	//cctv의 방향을 모두 선택했을때
	if (select.size() == cctv.size())
	{
		return Check(select);
	}

	//각 cctv의 방향(0~3)을 선택한다
	for (int i = 0; i < 4; i++)
	{
		select.push_back(i);
		ret = min(ret, Solve(select));
		select.pop_back();
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;
	vector<int> selected;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> input;
			board[i][j] = input;

			//cctv의 종류와 위치를 저장
			if (input >= 1 && input <= 5)
				cctv.push_back(make_pair(input, make_pair(i, j)));
		}

	//원본 board를 저장해 놓는다
	boardCopy(temp_board, board);

	cout << Solve(selected);

	return 0;
}