BOJ 풀이

[BOJ/백준 15683/C++] 감시

Vfly 2023. 3. 14. 21:23

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

 

[문제 요약]

- 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

 

- 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

 

- CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. - - CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

- CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

 

- 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

- 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

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

- 시간 제한 : 1초

- 메모리 제한 : 512MB

 

[문제 풀이]

이번 문제는 CCTV의 개수가 최대 8개고 격자판의 크기도 최대 8x8의 경우라 브루트포스 방식을 이용해 모든 경우의 수를 구해도 괜찮은 문제다.

 

필자는 다음과 같은 방식으로 구현하였다.

  • 입력을 받으면서 1이상 5이하인 값이 들어오면 카메라로 인식하여 vector<CCTV> camera 배열에 추가하였다. 이때 구조체 CCTV는 { CCTV의 타입, {위치}, vector<int> 방향 }을 멤버로 갖는 구조체이다.
  • 격자판에 CCTV가 1개 이상 존재할 경우 모든 카메라에 대하여 뱡향을 설정해 주었다. 이때 방향은 오른쪽이 0, 아래가 1, 왼쪽이 2, 위쪽이 3을 나타낸다.
    • CCTV의 타입이 2의 경우 멤버변수 dir에 0과 2가 들어가있다.
  • 재귀 방식을 이용하여 모든 카메라의 현재 상태에서 감시가 되는 부분의 값을 -1을 추가하는 방식으로 감시영역을 표시하였다.
    • 아래 그림과 같이 감시 구역이 겹치는 부분에 대해서는 값이 더 줄어들 것이다.
    • 이 처럼 -1을 더해준 이유는 재귀적으로 돌면서 기존에 있던 카메라들이 감시하는 구역을 유지시키기 위해 사용한 방법이다. 예를들어 아래쪽에 있는 카메라의 방향을 회전시키기 위해 세로방향에 표시해두었던 감시영역을 해제 시켜야 하는데 이때 값을 0으로 초기화 시켜버리면 위쪽에 있는 카메라가 감시하는 영역을 일부 해제 시켜버리게 된다. 따라서 해제 시킬때는 +1 감시구역을 표시할때는 -1로 함으로써 다른 CCTV에 영향을 안주는 방식인 것이다.

  • 모든 카메라에 대한 감시영역 표시가 끝나면 0인 부분을 전부 세어주고 이것의 최솟값으 구해서 출력하면 된다.

 

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

typedef struct CCTV
{
	int type;
	pii pos;
	vector<int> dir;
}CCTV;
int N, M, blk_cnt = 0, ans= INF;
int camerasize = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<int>> mp;
vector<CCTV> camera;

void set_dir()
{
	for (int i = 0; i < camera.size(); i++)
	{
		if (camera[i].type == 1) { camera[i].dir.push_back(0); }
		else if (camera[i].type == 2) { camera[i].dir.push_back(0); camera[i].dir.push_back(2); }
		else if (camera[i].type == 3) { camera[i].dir.push_back(0); camera[i].dir.push_back(1); }
		else if (camera[i].type == 4)
		{
			camera[i].dir.push_back(0); camera[i].dir.push_back(1); camera[i].dir.push_back(2);
		}
		else
		{
			for (int j = 0; j < 4; j++) camera[i].dir.push_back(j);
		}
	}
}

void calc(int num)
{	
	if (num > camerasize - 1)
	{
		int count = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (mp[i][j] == 0) count++;

		ans = min(ans, count);
		return;
	}
    //1번 3번 4번 타입의 카메라의 경우 회전 했을때 총 4가지의 경우가 나옴
	int time;
	if (camera[num].type == 1 || camera[num].type == 3 || camera[num].type == 4) time = 4;
	//2번의 경우는 2번만 회전해도 모든 경우가 나옴
    	else if (camera[num].type == 2) time = 2;
	else if (camera[num].type == 5) time = 1;

	for (int i = 0; i < time; i++)
	{
		vector<pii> tmp;
		for (int j = 0; j < camera[num].dir.size(); j++)
		{
			int y = camera[num].pos.first; int x = camera[num].pos.second;
			int direction = camera[num].dir[j];
			while (1)
			{
				int nx = x + dx[direction];
				int ny = y + dy[direction];

				if (nx < 0 || ny < 0 || nx >= M || ny >= N) break;
				if (mp[ny][nx] == 6) break;
				
				if (mp[ny][nx] <= 0) { mp[ny][nx] -= 1; tmp.push_back({ ny,nx }); }
				y = ny; x = nx;
			}
		}

		calc(num + 1);
	
    	//감시 구역 해제
		for (int h = 0; h < tmp.size(); h++)
		{
			mp[tmp[h].first][tmp[h].second] += 1;
		}
        //카메라 방향 회전
		for (int j = 0; j < camera[num].dir.size(); j++)
		{
			camera[num].dir[j] = (camera[num].dir[j] + 1) % 4;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;
	mp.resize(N); for (int i = 0; i < N; i++) mp[i].resize(M);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> mp[i][j];
			if (mp[i][j] >= 1 && mp[i][j] <= 5)
			{
				camera.push_back({ mp[i][j], {i,j} });
			}
		}
	}
	camerasize = camera.size();
	if(camerasize != 0) set_dir();
	calc(0);
	cout << ans;
}