풀이

0 : 빈칸 (사각지대)
1 : 한방향
2 : 반대
3 : 직각
4 : 3방향
5 : 4방향
6 : 벽
7 : CCTV 시야 범위

나는 7을 CCTV의 시야 범위로 정하고 문제를 풀었다.

DFS로 백트래킹 하면서 CCTV의 번호에 따라 방향을 정해주는 식으로 풀었다.

CCTV가 돌아가는 방향의 순서는 상관이 없다. 어짜피 4방향 다 돌게 될테니까

하지만 dx dy를 선언할 때 시계방향이든 반시계방향이든 한쪽으로 돌 수 있게 선언해주는게 편하다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
// CCTV
int k;

int Map[8][8] = { 0, };

// 동 남 서 북
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0,-1, 0 };

int Min = 999;

vector<pair<int, int>> v;

 //감시 1번, 2번, 3번, 4번, 5번
 //0 : 빈칸
 //1 : 한방향
 //2 : 반대
 //3 : 직각
 //4 : 3방향
 //5 : 4방향
 //6 : 벽
 //7 : CCTV 시야 범위


// x, y 에서의 CCTV 역할을 수행해준다.
void cctv(int x, int y, int dir)
{
	while (1)
	{
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			break;
		if (Map[nx][ny] == 6)
			break;
		// CCTV의 시야 범위를 7로 대체
		if (Map[nx][ny] >= 1 && Map[nx][ny] <= 5)
		{
			x += dx[dir];
			y += dy[dir];
			continue;
		}
		Map[nx][ny] = 7;

		x += dx[dir];
		y += dy[dir];
	}
}


void dfs(int cnt)
{
	if (cnt == v.size())
	{
		int count = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (Map[i][j] == 0)
					count++;
			}
		}
		Min = min(Min, count);
		return;
	}

	int x = v[cnt].first;
	int y = v[cnt].second;

	int bt[8][8] = { 0, };

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			bt[i][j] = Map[i][j];
		}
	}

	for (int i = 0; i < 4; i++)
	{
		if (Map[x][y] == 1)
		{
			cctv(x, y, i);
		}
		else if (Map[x][y] == 2)
		{
			cctv(x, y, i);
			cctv(x, y, (i + 2) % 4);
		}
		else if (Map[x][y] == 3)
		{
			cctv(x, y, i);
			cctv(x, y, (i + 1) % 4);
		}
		else if (Map[x][y] == 4)
		{
			cctv(x, y, i);
			cctv(x, y, (i + 1) % 4);
			cctv(x, y, (i + 2) % 4);
		}
		else if (Map[x][y] == 5)
		{
			cctv(x, y, i);
			cctv(x, y, (i + 1) % 4);
			cctv(x, y, (i + 2) % 4);
			cctv(x, y, (i + 3) % 4);
		}

		dfs(cnt + 1);

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				Map[i][j] = bt[i][j];
			}
		}
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> Map[i][j];
			if (Map[i][j] != 6 && Map[i][j] != 0)
			{
				// CCTV 면 좌표 저장
				v.push_back(make_pair(i, j));
			}
		}
	}

	dfs(0);
	cout << Min;

	return 0;
}

후기

DFS 문제는 쪼금 본게 있어서 할 만 했다.

백트래킹을 어떻게 하면 더 좋은 효율이 나오는지 알아보는게 좋을 것 같다.

지금은 각 재귀 마다 backtracking 배열을 생성해서 복사해주는 식으로 단순하게 구현했다.