[BOJ] 15683 감시

문제 해결/BOJ

[BOJ] 15683 감시

자잘 2019. 8. 17. 16:14

문제 출처: https://www.acmicpc.net/problem/15683

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

이번에도 구현이 난해해 보여서 건너 뛰었던 부루트 포스 감시 문제를 풀어보았습니다. 종만북을 본 이후로 자신감이 붙은 것 같아서 기분 좋네요 ㅎㅎ. 마음먹고 도전해보니 그리 어렵지는 않았습니다. CCTV의 종류와 보는 방향에 따라 감시할 수 있는 영역이 달라집니다. 이때 CCTV의 종류에 따라 감사 방향을 잘 정해서 감시할 수 없는 영역을 최소화하는 것이 문제였습니다. 주어진 CCTV의 종류와 좌표를 벡터에 저장한 다음 재귀를 통해서 각 CCTV의 보는 방향을 결정해 준 다음 CCTV의 종류에 맞추어서 직접 덮어보는 방식으로 풀었습니다.

	#include<iostream>
	#include<vector>
	#define INF 98765321
	using namespace std;

	int N, M, cctv, ans;

	int map[8][8];
	int tmap[8][8];

	int dx[4] = { 0,1,0,-1 };
	int dy[4] = { -1,0,1,0 };

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

	vector<CCTV> c;
	vector<int> vt;
	bool InRange(int y, int x)
	{
	return 0 <= x && x < M && 0 <= y && y < N;
	}

	void watch(int y, int x,int di)
	{
	int nx = x;
	int ny = y;

	while (InRange(ny, nx) && tmap[ny][nx] != 6)
	{
	tmap[ny][nx] = -1;
	nx += dx[di];
	ny += dy[di];
	}
	}

	void check(int i, int di)
	{
	int type = c[i].type;
	int y = c[i].y;
	int x = c[i].x;

	if (type == 1)
	{
	watch(y, x, di);
	}
	else if (type == 2)
	{
	watch(y, x, di);
	watch(y, x, (di + 2) % 4);
	}
	else if (type == 3)
	{
	watch(y, x, di);
	watch(y, x, (di + 1) % 4);
	}
	else if (type == 4)
	{
	watch(y, x, di);
	watch(y, x, (di + 1) % 4);
	watch(y, x, (di + 3) % 4);
	}
	else
	{
	watch(y, x, di);
	watch(y, x, (di + 1) % 4);
	watch(y, x, (di + 2) % 4);
	watch(y, x, (di + 3) % 4);
	}

	return;
	}

	void back()
	{
	if (vt.size() >= cctv)
	{
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	tmap[i][j] = map[i][j];
	}
	}

	for (int i = 0; i < cctv; i++)
	{
	check(i, vt[i]);
	}

	int temp = 0;

	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	if (!tmap[i][j])
	temp++;
	}
	}

	ans = (ans < temp) ? ans : temp;
	return;
	}

	for (int i = 0; i < 4; i++)
	{
	vt.push_back(i);
	back();
	vt.pop_back();
	}
	}

	int main(void)
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	cin >> map[i][j];

	if (1 <= map[i][j] && map[i][j] < 6)
	{
	cctv++;
	c.push_back({ i,j,map[i][j] });
	}
	}
	}

	ans = INF;
	back();
	cout << ans;
	}

view raw 15683.cpp hosted with ❤ by GitHub