[백준 15683] 감시

문제 파악

 

사무실은 NxM

그리고 그 사무실은 총 k개의 cctv설치

cctv는 총 5종류

1번은 한쪽 방향만 감시할 수 있다.

2번은 두방향 감시 단, 직선형태로 감시

3번은 두방향 감시 단, 직각 형태로 감시

4번은 세방향

5번은 네방향

cctv는 벽을 통과 못함 cctv는 통과 할 수 있음

cctv는 회전가능 단 90도방향으로 즉 방향이 가로또는 세로 방향

0번은 빈칸, 6번은 벽, 1~5는 cctv번호

출력=> cctv방향을 적절히 정해서 사각지대의 최소 크기를 구해야한다.

입력=> 1<=N,M<=8

cctv개수는 8개 안넘음

---

문제 해결

사무실을 입력을 받다가 cctv위치가 나오면 그 위치를 미리 벡터에 저장하여 완전탐색할때 계속 cctv방향을 바꿔 갈 것이다.

즉 2번 카메라의 위치를 파악했다면 왼쪽 오른쪽을 감시하는 카메라 였다가 다음 각도에서는 위쪽 아래쪽을 감시하는 카메라가 될것이다.

그래서 현재 바라보고 있는 방향도 정해준다. 왼쪽 오른쪽을 감시하는 2번카메라라고 명시

//0은 오른쪽 1은 아래 2는 왼 3은 위

see[n\][m\][0] = true

see[n\][m\][2] = true

1번카메라 같은 경우

하나만

see[n\][m\][0] = true

그리고나서 1번카메라 각도 0도 일때는

오른쪽을 바라보게 되고

각도 90도 일때는

아래쪽을 바라보게 되고

각도 180도일때는

왼쪽

각도 270도

위쪽

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
int office[8][8];
int copy_office[8][8];

bool see[8][8][4];
vector<pair<int, int>> cctv;
vector<int> angle;
int result;
pair<int, int> go[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //오,아,왼,위
void count_zero() 
{
	int res = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (copy_office[i][j] == 0) res++;

		}
	}

	if (res < result) result = res;
}
void copy()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			copy_office[i][j] = office[i][j];

		}
	}
}
void dfs(int cnt) {
	//내가 저장할때 시시티비의 각도를 정해놓았다. 
	//예를들어 시시티비가 2개이면
	// 1번 카메라 , 3번카메라
	//1번 카메라의 각도는 현재 오른쪽 3번카메라의 각도는 오,아,왼
	
	//이 카메라들은 1번이 오른쪽 볼때 3번이 (오,아,왼) or (아,왼,위) or (왼,위,오) or (위,오,아) 즉 각도가 (0도 0도) (0도 90도) (0도 180도) (0도 270도)
	//또 1번이 아래쪽을 볼때 3번이 (오,아,왼) or (아,왼,위) or (왼,위,오) or (위,오,아) 즉 각도가 (90도 회전, 0도)
	// 1번이 왼쪽볼때 3번이 (오,아,왼) or (아,왼,위) or (왼,위,오) or (위,오,아)
	//1번이 위쪽 볼때 3번이 (오,아,왼) or (아,왼,위) or (왼,위,오) or (위,오,아)
	//이런식으로 하려면 각도를 기억하고 있어야한다 
	//몇번째로 보는 카메라 그리고 회전?
	//cnt가 0일때 첫번째로 보는 카메라 각도 0 => cnt가 1일때 두번째로 보는 카메라 각도 0 =>cnt가 2일때 카메라 개수 2와 일치하므로 이때는 완성했으므로 0의 개수를 센다
	if (cnt == cctv.size())
	{
		for (int i = 0; i < cctv.size(); i++)
		{
			//모든 카메라들을 진행시켜
			int n = cctv[i].first;
			int m = cctv[i].second;

			
				//처음에는 각도가 0이니깐 오른쪽을 볼것이다 근데 카메라마다 방향을 여러개 보는 카메라도 있으니 see배열 이용
				for (int k = 0; k < 4; k++)
				{
				

					//보고 있는 방향이 맞다면
					if (see[n][m][k])
					{
						//일단 1번카메라라고 하면 오른쪽을 보고 있고 각도가 0부터 시작한다 즉 
						int nextN = n + go[(k + angle[i]) % 4].first;
						int nextM = m + go[(k + angle[i]) % 4].second;

						//cout << nextN << " " << nextM << '\n';

						while (true) {

							//유효성 체크
							if (nextN < 0 || nextN >= N || nextM < 0 || nextM >= M)break;

							//이제 그 방향으로 가면서 체크
							int pos = copy_office[nextN][nextM];
							if (pos == 0)
							{
								copy_office[nextN][nextM] = -1;
							}
							else if(pos == 6)
							{
								break;
							}
							
							nextN = nextN + go[(k + angle[i]) % 4].first;
							nextM = nextM + go[(k + angle[i]) % 4].second;
							


						}
						
					}
				}
				 
			

		}


		//모든 카메라를 탐색했으니 0의 개수를 세야한다.
		count_zero();
		//복사본 배열 초기화
		copy();
		return;

	}
	for (int i = 0; i < 4; i++)
	{
		//백트래킹 방식
		angle.push_back(i);
		dfs(cnt + 1);
		angle.pop_back();
		//{0,0},{0,1},{0,2},{0,3} ,{1,0},{1,1}...
	}
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M;

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

			if (1 <= office[i][j] && office[i][j] <= 5) 
			{
				//시시티비의 위치 넣기
				cctv.push_back({ i,j });

				//시시티비가 바라보고 있는 방향 미리 넣기
				switch (office[i][j])
				{
				case 1:
					see[i][j][0] = true;
					break;
				case 2:
					see[i][j][0] = true;
					see[i][j][2] = true;
					break;
				case 3:
					see[i][j][0] = true;
					see[i][j][1] = true;
					break;
				case 4:
					see[i][j][0] = true;
					see[i][j][1] = true;
					see[i][j][2] = true;
					break;
				case 5:
					see[i][j][0] = true;
					see[i][j][1] = true;
					see[i][j][2] = true;
					see[i][j][3] = true;
					break;
				}

			}



			

		}
	}
	result = 10000;
	//사무실 복사본 만들기
	copy();
	dfs(0);

	cout << result;

}