[백준알고리즘] 15683번: 감시 -C++

[백준알고리즘] 15683번: 감시 -C++

15683번: 감시 (acmicpc.net)

15683번: 감시

예전에 파이썬으로 풀다가 무슨 일 때문인지 하다가 포기했던 문제다. C++로 새롭게 푸는데 생각보다 쉽게 풀려서 당황스럽다.

 

시간제한은 1초이지만 메모리 제한은 큰 문제다. 시간제한 때문에 고민을 좀 했다. 하지만 한 가지 조건 덕분에 완전 탐색(브루트포스) 방식으로 문제를 해결할 수 있었다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제를 풀 수 있는 중요한 조건

문제를 해결할 수 있었던 조건은 다음과 같다.

CCTV의 최대 개수는 8개를 넘지 않는다.

 

이것이 왜 문제를 풀 수 있는 도움을 주냐면 사무실의 크기는 최대 \( 8 \times 8 = 64 \)의 크기다. 여기서 각 위치마다 CCTV가 존재한다고 하고, 각 CCTV 마다 최대 4방향의 경우를 살펴봐야 하기 때문에 \( 4^{64} \)의 연산을 수행해야 하기 때문에 1초는 턱없이 부족하게 된다.

 

하지만, CCTV의 개수가 최대 8개로 제한이 되어있기 때문에 완전탐색을 시도할 최대 경우의 수는 제한되게 된다. 각 CCTV 마다 최대 4 방향을 살펴야 하기 때문에, 최대 \( 4^8 \)의 경우만 따져주면 된다. 이는 1초의 제한에 걸리지 않을 것이다.

 

---

 

문제 풀이

먼저, 카메라의 종류에 따라 바라볼 수 있는 방향에 대해서 선언을 해주었다.

예를 들어서, 1번 카메라는 {상}, {하}, {좌}, {우} 방향을 한 번씩 살펴보게 된다. 

반면에 2번 카메라는 {상, 하}의 방향과 {좌, 우}의 방향을 묶어서 볼 수 있다.

 

이런 식으로 동시에 볼 수 있는 방향들을 묶어서 pair를 사용해 Unit Vector로 정의를 해놓았다. 

 

그런 다음, 입력받는 사무실의 상태에서 카메라들의 위치에 대해서 DFS 방식으로 브루트포스를 시도한다. 모든 경우의 수를 따져서 가장 사각지대가 적을 때의 사각지대 영역의 크기를 출력한다.

 

이때 각 카메라의 위치에서 감시 영역을 체크하는데, 주어진 방향에 대해서 새롭게 감시영역으로감시 영역으로 추가되는 부분을 확인해준다. 새롭게 감시 영역으로 추가되는 부분이란, 다른 카메라가 위치해있거나 다른 카메라가 이미 감시한 영역이 아닌 사각지대였으나 새롭게 감시를 할 수 있게 된 영역이다. 

그런 다음, 다른 카메라로 반복해서 확인해주는 과정을 거치고, 다른 방향으로도 반복해서 수행한다.

 

그렇게 모든 카메라의 경우의 수를 따졌을 때마다 최소 감시영역인지 확인한 뒤 갱신해주는 과정을 통해 DFS 방식을 완성한다.

 

사실 카메라 방향들이 다양하게 있어서 그렇지 쉽게 DFS 브루트포스 방식으로 문제를 해결할 수 있었다.

 

아래는 C++로 해결한 코드다.

#include <iostream>
#include <vector>

std::vector<std::vector<std::vector<std::pair<int, int>>>> direction = {
	{},
	{
		{std::make_pair(1, 0)},
		{std::make_pair(-1, 0)},
		{std::make_pair(0, 1)},
		{std::make_pair(0, -1)},
	},
	{
		{std::make_pair(1, 0), std::make_pair(-1, 0)},
		{std::make_pair(0, 1), std::make_pair(0, -1)}
	},
	{
		{std::make_pair(1, 0), std::make_pair(0, 1)},
		{std::make_pair(-1, 0), std::make_pair(0, 1)},
		{std::make_pair(-1, 0), std::make_pair(0, -1)},
		{std::make_pair(1, 0), std::make_pair(0, -1)}
	},
	{
		{std::make_pair(1, 0), std::make_pair(0, 1), std::make_pair(-1, 0)},
		{std::make_pair(1, 0), std::make_pair(0, -1), std::make_pair(-1, 0)},
		{std::make_pair(0, 1), std::make_pair(1, 0), std::make_pair(0, -1)},
		{std::make_pair(0, 1), std::make_pair(-1, 0), std::make_pair(0, -1)}
	},
	{
		{std::make_pair(1, 0), std::make_pair(0, 1), std::make_pair(-1, 0), std::make_pair(0, -1)}
	}
};

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int countBlindSpot(std::vector<std::vector<int>>& map)
{
	int h = map.size();
	int w = map[0].size();
	
	int count = 0;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (map[i][j] == 0)
				count++;

	return count;
}

int getMinBlindSpot(std::vector<std::vector<int>>& map, 
					const std::vector<std::pair<int, int>>& cameraList, const int cameraIndex)
{
	if (cameraList.size() == cameraIndex)
		return countBlindSpot(map);

	int height = map.size();
	int width = map[0].size();
	int x = cameraList[cameraIndex].first;
	int y = cameraList[cameraIndex].second;
	int cameraType = map[y][x];
	
	int minSpot = 64;
	for (auto d : direction[cameraType])
	{
		std::vector<std::pair<int, int>> watch;

		// 카메라 있는 곳과 이미 감시 영역인 부분은 지나고, 벽이 있으면 종료
		for (auto dxdy : d)
		{
			int tx = x, ty = y;
			int dx = dxdy.first;
			int dy = dxdy.second;

			while (0 <= tx + dx && tx + dx < width && 0 <= ty + dy && ty + dy < height)
			{
				tx += dx;
				ty += dy;

				if (6 == map[ty][tx])
					break;

				if (0 != map[ty][tx])
					continue;

				map[ty][tx] = -1;
				watch.push_back(std::make_pair(tx, ty));
			}
		}

		minSpot = std::min(minSpot, getMinBlindSpot(map, cameraList, cameraIndex + 1));

		// 되돌리기
		while (watch.size())
		{
			std::pair<int, int> position = watch.back(); watch.pop_back();
			map[position.second][position.first] = 0;
		}
	}
	
	return minSpot;
}


void solve(void)
{
	int n, m;
	std::cin >> n >> m;

	std::vector<std::pair<int, int>> cameraList;
	std::vector<std::vector<int>> map(n, std::vector<int>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			std::cin >> map[i][j];

			if (0 < map[i][j] && map[i][j] < 6)
				cameraList.push_back(std::make_pair(j, i));
		}

	std::cout << getMinBlindSpot(map, cameraList, 0);
}