[백준 C++] 15683 감시 - 백트래킹

15683번: 감시

---

 

문제풀이

 

구현할 것이 많은 시뮬레이션 & 브루트포스 & 백트래킹 유형의 문제입니다.

 

카메라의 개수는 많지 않기 때문에, 각 카메라의 방향을 완전탐색(브루트포스 & 백트래킹)으로

모든 각도에서 지정해보고 그 중 사각지대의 최소값을 구하면 됩니다.

 

사각지대를 구하기 전에 각 카메라의 방향에 따른 사무실의 상태를 구할 때 많은 구현이 필요합니다.

각 카메라가 사무실을 스캔할 때, 카메라의 종류에 따라 먼저 분류하고

지정된 스캔 방향, 횟수에 따라서 사무실의 상태를 구하도록 했습니다.

---

코드

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

typedef pair<int, int> p;
typedef pair<int, p> info;

const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };

int N, M;
int Map[8][8];

int C;
info Cam[8];
int Dir[8];

int Min;
int Sol[8][8];

void Scanning(int Idx, int D, int MulInverse = 1)
{
	int R = Cam[Idx].second.first, C = Cam[Idx].second.second;

	int i = 1;
	while (true)
	{
		int NR = R + DY[D] * i * MulInverse;
		int NC = C + DX[D] * i * MulInverse;
		if (NR < 0 || NR > N - 1 || NC < 0 || NC > M - 1
			|| Sol[NR][NC] == 6)
		{
			break;
		}

		if (Sol[NR][NC] == 0)
		{
			Sol[NR][NC] = -1;
		}

		++i;
	}
}

int CountBlank()
{
	memcpy(Sol, Map, sizeof(Sol));

	for (int i = 0; i < C; ++i)
	{
		int D = Dir[i];
		int D2 = (D + 1 > 3) ? 0 : D + 1;

		switch (Cam[i].first)
		{
		case 1:
			Scanning(i, D);
			break;
		case 2:
			Scanning(i, D);
			Scanning(i, D, -1);
			break;
		case 3:
			Scanning(i, D);
			Scanning(i, D2);
			break;
		case 4:
			Scanning(i, D);
			Scanning(i, D, -1);
			Scanning(i, D2);
			break;
		case 5:
			Scanning(i, D);
			Scanning(i, D, -1);
			Scanning(i, D2);
			Scanning(i, D2, -1);
			break;
		}
	}

	int Cnt = 0;

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

	return Cnt;
}

void Backtracking(int Idx)
{
	if (Idx == C)
	{
		Min = min(Min, CountBlank());
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		Dir[Idx] = i;
		Backtracking(Idx + 1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M;

	Min = N * M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			int Num;
			cin >> Num;
			Map[i][j] = Num;

			if (Num >= 1 && Num <= 5)
			{
				Cam[C] = info(Num, p(i, j));
				++C;
				--Min;
			}
			else if (Num == 6)
			{
				--Min;
			}
		}
	}

	Backtracking(0);

	cout << Min;
}