[BOJ] 15683 감시

Link https://www.acmicpc.net/problem/15683

Note

5 종류의 최대 8개의 감시카메라가 최대 8 x 8의 정사각형 방을 감시하는데 최소 사각지대를 구하는 문제이다.
문제 내용도 간단하고 무엇보다 설명이 자세하게 잘 되어있던 문제
예제 또한 많았기에 예제가 정상적으로 전부 돌아간다면 반례는 크게 생각을 하지 않아도 될 것 같다.

재귀적 구조로 순열을 구현해 각 상황에 맞게 사각지대를 확인하는 방식으로 구현했다.

원래 맵 자체를 건드리면 안되기에
8 by 8 bool map을 매번 새로 생성해 결과를 확인 했는데
최악의 경우 400만번이 넘는 경우가 나와 시간초과를 예상했으나 무난하게 잘 돌아갔다.

문제 자체를 푸는데 시간을 오래 썼다기보다 카메라가 감시하는 방향을 최대한 간결하게 구현 하려는 데에 시간을 많이 썼다.

알고리즘

1. 방의 구조를 입력 받으며 cctv의 위치와 타입을 저장하여 배열에 저장한다.
2. 순열을 통해 cctv 타입마다 방향성을 지정해 준다. ( 2번은 - 상하/ 좌우 , 5번은 - 방향성 없음, 1 3 4번은 , 4방향성 전부 )
3. 순열이 완성된 경우 cctv 타입에 맞게 바라볼수 있는 방향을 지정하는 bool 배열을 초기화
4. 벽에 막히거나 범위를 벗어나는 경우를 판별하기 위한 bool 배열을 생성
5. 모든 방향을 볼수 없거나 벽에 막혀있는 경우가 나올 때 까지 사각지대를 감소 시킨다.
6. 사각지대가 아닌 지점의 개수를 헤아려 현재 최소 사각지대와 비교후 최소 사각지대를 갱신
7. 최소 사각지대를 출력

소스코드

#include <iostream>

using namespace std;

struct CCTV
{
	int x;
	int y;
	int type;

	CCTV() : x(0), y(0), type(0) {};
	CCTV(int x, int y, int type) : x(y), y(x), type(type) {};
};

CCTV cctvs[8];

int see[8];
int rooms[8][8];
int cctvCount;
int myMin = 65;
int cctvSee[8];
int n, m;
const int posX[4] = { 0, 1, 0, -1 };
const int posY[4] = { 1, 0, -1, 0 };

void func(int pos)
{
	if (pos == cctvCount)
	{
		int count = 0;

		bool blind[8][8];

		for (int i = 0; i < n; i++)
			fill_n(blind[i], m, true);

		for (int i = 0; i < pos; i++)
		{
			blind[cctvs[i].x][cctvs[i].y] = false;
			bool canShow[4] = { false, false, false, false };
			bool blocked[4] = { false, false, false, false };

			if (cctvs[i].type == 1)
				canShow[cctvSee[i] - 1] = true;
			else if (cctvs[i].type == 2)
				canShow[cctvSee[i] - 1] = canShow[(cctvSee[i] + 1) % 4] = true;
			else if (cctvs[i].type == 3)
				canShow[cctvSee[i] - 1] = canShow[cctvSee[i] % 4] = true;
			else if (cctvs[i].type == 4)
				canShow[cctvSee[i] - 1] = canShow[cctvSee[i] % 4] = canShow[(cctvSee[i] + 1) % 4] = true;
			else
				for (int j = 0; j < 4; j++)
					canShow[j] = true;

			for (int step = 1; (canShow[0] && !blocked[0]) || (canShow[1] && !blocked[1]) || (canShow[2] && !blocked[2]) || (canShow[3] && !blocked[3]); step++)
			{
				for (int j = 0; j < 4; j++)
				{
					if (blocked[j] || !canShow[j]) // 막혔거나 감시가 불가하면 continue
						continue;

					int x = cctvs[i].x + (posX[j] * step);
					int y = cctvs[i].y + (posY[j] * step);

					if (0 <= x && x < n && 0 <= y && y < m) // 범위를 넘지 않으면 진행
					{
						if (rooms[x][y] == 6)
						{
							blocked[j] = true;
							continue;
						}
						if (!blind[x][y])
							continue;

						blind[x][y] = false;
					}
					else
						blocked[j] = true;
				}
			}
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (blind[i][j] && rooms[i][j] != 6)
					count++;

		if (myMin > count)
			myMin = count;
	}
	else
	{
		if (cctvs[pos].type == 2) // 양방향 cctv의 경우 2가지 경우
		{
			for (int i = 0; i < 2; i++)
			{
				cctvSee[pos]++;
				func(pos + 1);
			}
			cctvSee[pos] = 0;
		}
		else if (cctvs[pos].type == 5) // 전방향 cctv의 경우 1가지 경우
		{
			func(pos + 1);
		}
		else
		{
			for (int i = 0; i < 4; i++) // 나머지 cctv는 4가지 경우
			{
				cctvSee[pos]++;
				func(pos + 1);
			}
			cctvSee[pos] = 0;
		}
	}
}

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

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> rooms[i][j];
			if (rooms[i][j] != 0 && rooms[i][j] != 6)
			{
				cctvs[cctvCount].x = i;
				cctvs[cctvCount].y = j;
				cctvs[cctvCount].type = rooms[i][j];
				cctvCount++;
			}
		}

	func(0);

	cout << myMin;

	return 0;
}

2019-01-09 02:30:00에 Tistory에서 작성되었습니다.