백준 15683 - 감시

문제링크

• 백준 15683

문제설명

• 링크 참고

문제접근

• CCTV 별로 감시 가능한 방향 조합을 미리 정의해둔다.
  • table[cctv][type] 은 cctv 번의 감시 가능한 타입의 방향 정보들을 담는다.
  • 예를 들어, 1번 cctv 의 경우 한가지 방향만 담기고 2,3번 cctv의 경우 2가지 방향, 4번 cctv의 경우 3가지 방향, 5번 cctv 의 경우 4가지 방향이 담긴다.
  • 한번에 여러 방향을 감시하는 cctv 가 있으므로 인접리스트 형태로 데이터를 담는다.
• 입력 받는 CCTV 의 위치 정보를 담아둔다. cctv 번호를 바로바로 추출하기 위함이다.
• allCases[cctv] 는 cctv 번의 선택 가능한 감시 type 종류를 담는다.
  • 1번 cctv의 경우 감시 가능한 모든 type 은 상, 하, 좌, 우 4가지 타입이 가능하다.
  • 2번 cctv의 경우 좌우, 상하 2가지 타입이 가능하다.
  • 3번 cctv의 경우 상우, 하우, 하좌, 상좌 4가지 타입이 가능하다.
  • 4번 cctv의 경우 상좌우, 상하우, 하좌우, 상하좌 4가지 타입이 가능하다.
  • 5번 cctv의 경우 상하좌우 1가지 타입이 가능하다.
• 백트래킹으로 cctv 별 모든 감시 타입에 대해서 탐색하고, 최소 사각지대 개수를 구한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <queue>
#include <climits>

#define MAX_N_M 8
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
#define CCTV_MAX 6 // 1 ~ 5번
#define CASES_MAX 4
#define EMPTY 0
#define WALL 6
#define CHECK 7 // cctv 로 감시된 영역
using namespace std;

int N, M;
int board[MAX_N_M][MAX_N_M];
int cboard[MAX_N_M][MAX_N_M];
vector<pair<int, int>> cctvPos;
vector<int> table[CCTV_MAX][CASES_MAX];
vector<int> allCases[CCTV_MAX];
vector<int> cand;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool visited[64];

void input()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			cin >> board[r][c];
			if (board[r][c] > 0 && board[r][c] < 6) cctvPos.push_back(make_pair(r, c));
		}
	}
	memset(visited, false, sizeof(visited));
}

void initCCTV()
{
	table[1][0].push_back(UP);
	table[1][1].push_back(DOWN);
	table[1][2].push_back(LEFT);
	table[1][3].push_back(RIGHT);
	allCases[1].push_back(0);
	allCases[1].push_back(1);
	allCases[1].push_back(2);
	allCases[1].push_back(3);

	table[2][0].push_back(UP);
	table[2][0].push_back(DOWN);
	table[2][1].push_back(LEFT);
	table[2][1].push_back(RIGHT);
	allCases[2].push_back(0);
	allCases[2].push_back(1);
	
	table[3][0].push_back(UP);
	table[3][0].push_back(RIGHT);
	table[3][1].push_back(RIGHT);
	table[3][1].push_back(DOWN);
	table[3][2].push_back(DOWN);
	table[3][2].push_back(LEFT);
	table[3][3].push_back(LEFT);
	table[3][3].push_back(UP);
	allCases[3].push_back(0);
	allCases[3].push_back(1);
	allCases[3].push_back(2);
	allCases[3].push_back(3);

	table[4][0].push_back(LEFT);
	table[4][0].push_back(UP);
	table[4][0].push_back(RIGHT);
	table[4][1].push_back(UP);
	table[4][1].push_back(RIGHT);
	table[4][1].push_back(DOWN);
	table[4][2].push_back(RIGHT);
	table[4][2].push_back(DOWN);
	table[4][2].push_back(LEFT);
	table[4][3].push_back(DOWN);
	table[4][3].push_back(LEFT);
	table[4][3].push_back(UP);
	allCases[4].push_back(0);
	allCases[4].push_back(1);
	allCases[4].push_back(2);
	allCases[4].push_back(3);

	table[5][0].push_back(UP);
	table[5][0].push_back(RIGHT);
	table[5][0].push_back(DOWN);
	table[5][0].push_back(LEFT);
	allCases[5].push_back(0);
}

void updateMap(int sx, int sy, int dir)
{
	int nx = sx + dx[dir];
	int ny = sy + dy[dir];

	while (true) {
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
		if (board[nx][ny] == WALL) break;
		if (board[nx][ny] == EMPTY) cboard[nx][ny] = CHECK;
		nx += dx[dir];
		ny += dy[dir];
	}
}

void startMonitor(int sx, int sy, int dirNumber)
{
	int cctv = board[sx][sy];

	for (auto dir : table[cctv][dirNumber]) {
		updateMap(sx, sy, dir);
	}
}

int countNoCheckArea()
{
	int ret = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (cboard[r][c] == EMPTY) ret++;
		}
	}
	return ret;
}

int getNoVisibleAreaNum()
{
	memcpy(cboard, board, sizeof(board));
	for (int i = 0; i < cand.size(); i++) {
		int sx = cctvPos[i].first;
		int sy = cctvPos[i].second;
		int dirNumber = cand[i];
		startMonitor(sx, sy, dirNumber);
	}
	return countNoCheckArea();
}

int dfs(int v)
{
	if (v == cctvPos.size()) {
		return getNoVisibleAreaNum();
	}

	int ret = INT_MAX;
	for (int i = v; i < cctvPos.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		int cctv = board[cctvPos[i].first][cctvPos[i].second];
		for (int j = 0; j < allCases[cctv].size(); j++) {
			cand.push_back(allCases[cctv][j]);
			ret = min(ret, dfs(i + 1));
			cand.pop_back();
		}
		visited[i] = false;
	}
	return ret;
}

int main()
{
	input();
	initCCTV();
	cout << dfs(0) << endl;
	return 0;
}