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

15683번: 감시

---

 

문제풀이

 

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

 

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

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

 

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

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

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

---

코드

cpp

#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;
}