[SWEA] 감시

문제링크 : https://www.acmicpc.net/problem/15683

💻 문제 풀이 : C++

#include <iostream>
#include <vector>
#define MAX 10
using namespace std;

struct CCTV {
	int row;
	int col;
	int cctv;
	int dir;
};

vector<CCTV> camera;
vector<int> dir;
int N, M;
int MAP[MAX][MAX];
int ORIG[MAX][MAX];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int minSpace = 2134567890;

int getBlackSpace()
{
	int ans = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (MAP[i][j] == 0)
				ans++;
	return ans;
}

void drawMAP(int sr, int sc, int cctv, int dir)
{
	if (cctv == 1)
	{
		int nr = sr;
		int nc = sc;
		while (1)
		{
			nr += dr[dir];
			nc += dc[dir];
			if (MAP[nr][nc] == 6 || nr < 0 || nc < 0 || nr >= N || nc >= M) break;
			if (0 < MAP[nr][nc] && MAP[nr][nc] < 6) continue;
			MAP[nr][nc] = 7;
		}
	}
	else if (cctv == 2)
	{
		for (int i = 0; i < 4; i++)
		{
			if (dir%2 == 0 && (i == 1 || i == 3)) continue;
			else if (dir%2 == 1 && (i == 0 || i == 2)) continue;
			int nr = sr;
			int nc = sc;
			while (1)
			{
				nr += dr[i];
				nc += dc[i];
				if (MAP[nr][nc] == 6 || nr < 0 || nc < 0 || nr >= N || nc >= M) break;
				if (0 < MAP[nr][nc] && MAP[nr][nc] < 6) continue;
				MAP[nr][nc] = 7;
			}
		}
	}
	else if (cctv == 3)
	{
		for (int i = 0; i < 4; i++)
		{
			if (dir == 0 && (i == 2 || i == 3)) continue;
			else if (dir == 1 && (i == 3 || i == 0)) continue;
			else if (dir == 2 && (i == 0 || i == 1)) continue;
			else if (dir == 3 && (i == 1 || i == 2)) continue;
			int nr = sr;
			int nc = sc;
			while (1)
			{
				nr += dr[i];
				nc += dc[i];
				if (MAP[nr][nc] == 6 || nr < 0 || nc < 0 || nr >= N || nc >= M) break;
				if (0 < MAP[nr][nc] && MAP[nr][nc] < 6) continue;
				MAP[nr][nc] = 7;
			}
		}
	}
	else if (cctv == 4)
	{
		for (int i = 0; i < 4; i++)
		{
			if (i == dir) continue;
			int nr = sr;
			int nc = sc;
			while (1)
			{
				nr += dr[i];
				nc += dc[i];
				if (MAP[nr][nc] == 6 || nr < 0 || nc < 0 || nr >= N || nc >= M) break;
				if (0 < MAP[nr][nc] && MAP[nr][nc] < 6) continue;
				MAP[nr][nc] = 7;
			}
		}
	}
	else if (cctv == 5)
	{
		for (int i = 0; i < 4; i++)
		{
			int nr = sr;
			int nc = sc;
			while (1)
			{
				nr += dr[i];
				nc += dc[i];
				if (MAP[nr][nc] == 6 || nr < 0 || nc < 0 || nr >= N || nc >= M) break;
				if (0 < MAP[nr][nc] && MAP[nr][nc] < 6) continue;
				MAP[nr][nc] = 7;
			}
		}
	}
}

void DFS(int level)
{
	if (level >= camera.size())
	{
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				MAP[i][j] = ORIG[i][j];
		for (int i = 0; i < camera.size(); i++)
			drawMAP(camera[i].row, camera[i].col, camera[i].cctv, dir[i]);
		int tmp = getBlackSpace();
		if (minSpace > tmp) minSpace = tmp;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		dir.push_back(i);
		DFS(level + 1);
		dir.pop_back();
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> ORIG[i][j];
			if (0 < ORIG[i][j] && ORIG[i][j] < 6)
			{
				camera.push_back({ i, j, ORIG[i][j] });
			}
		}
	}

	DFS(0);
	cout << minSpace << endl;

	return 0;
}