(c++)백준 15683번: 감시

www.acmicpc.net/problem/15683

15683번: 감시

[풀이]

문제에 주어진 규칙대로 구현하면 되는 문제였다.

1. 감시카메라들 방향 결정

2. 감시구역 표시

3. 사각지대 크기 구해서 최솟값 갱신

 

1. 감시카메라들 방향 결정

- dfs로 모든 감시카메라들의 방향 경우의 수를 탐색

- 처음에 사무실 상태를 입력 받으면서 감시카메라 위치와 종류를 벡터에 동시에 저장하였다.

- 벡터에 저장한 순서대로 감시카메라 방향을 결정하였다.

- 방향은 cctvDir[]에 벡터에서의 인덱스와 같은 인덱스에 저장하여서 감시구역 표시할 때 감시카메라 종류와 방향을 한 인덱스로 알 수 있게 하였다.

 

2. 감시구역 표시

- dfs 백트래킹을 해야하므로 배열 Map을 배열 cMap에 복사하여 사용하였다.

- 순서대로 감시카메라가 바라보는 방향의 모든 빈칸을 -1로 채워주었다.

 

3. 사각지대 크기 구해서 최솟값 갱신

- cMap 배열에서 0의 개수 세기

 

※반례 만드는 법은 아직 잘 모르겠지만 각각 감시카메라가 제대로 감시를 하는지 cMap 배열을 출력하여 확인하면서 했다.

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

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

struct PosD {
	int x, y;
};

int N, M;
int Map[8][8];
int cMap[8][8];
vector<CCTV>cctv;//cctv정보 저장
int cctvDir[9];//정해진 cctv방향 저장
//1번 CCTV방향 위,아래,왼,오
const int OneD[][2] = { {-1,0},{1,0},{0,-1},{0,1} };
//2번 CCTV방향 ㅣ ㅡ
const int TwoD[][4] = { {-1,0,1,0}, {0,-1,0,1} };
//3번 CCTV방향 ㄴ ㄱ 대칭
const int ThreeD[][4] = { {-1,0,0,1},{0,1,1,0},{1,0,0,-1},{0,-1,-1,0} };
//4번 CCTV방향 ㅗ ㅏ ㅜ ㅓ
const int FourD[][6] = { {0,-1,-1,0,0,1},{-1,0,0,1,1,0},{0,-1,0,1,1,0},{0,-1,-1,0,1,0} };
//5번 CCTV방향 +
const int FiveD[][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int cctvCnt = 0;
int Min = 987654321;

void copyMap() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cMap[i][j] = Map[i][j];
		}
	}
}

int countArea() {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (cMap[i][j] == 0)
				cnt++;
		}
	}
	return cnt;
}

void markArea() {
	copyMap();
	//각 cctv마다 감시하는 구역 -1로 표시
	for (int i = 0; i < cctvCnt; i++) {
		//1번 cctv인 경우
		if (cctv[i].t == 1) {
			int nx = cctv[i].x + OneD[cctvDir[i]][0];
			int ny = cctv[i].y + OneD[cctvDir[i]][1];
			//다른 cctv나 벽과 경계에 부딪히기 전까지
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			while (cMap[nx][ny] != 6) {
				cMap[nx][ny] = -1;
				nx += OneD[cctvDir[i]][0];
				ny += OneD[cctvDir[i]][1];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					break;
			}
		}
		//2번 cctv
		else if (cctv[i].t == 2) {
			for (int d = 0; d <= 2; d += 2) {
				int nx = cctv[i].x + TwoD[cctvDir[i]][d];
				int ny = cctv[i].y + TwoD[cctvDir[i]][d + 1];
				//다른 cctv나 벽과 경계에 부딪히기 전까지
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;
				while (cMap[nx][ny] != 6) {
					cMap[nx][ny] = -1;
					nx += TwoD[cctvDir[i]][d];
					ny += TwoD[cctvDir[i]][d + 1];
					if (nx < 0 || nx >= N || ny < 0 || ny >= M)
						break;
				}
			}
		}
		//3번
		else if (cctv[i].t == 3) {
			for (int d = 0; d <= 2; d += 2) {
				int nx = cctv[i].x + ThreeD[cctvDir[i]][d];
				int ny = cctv[i].y + ThreeD[cctvDir[i]][d + 1];
				//다른 cctv나 벽과 경계에 부딪히기 전까지
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;
				while (cMap[nx][ny] != 6) {
					cMap[nx][ny] = -1;
					nx += ThreeD[cctvDir[i]][d];
					ny += ThreeD[cctvDir[i]][d + 1];
					if (nx < 0 || nx >= N || ny < 0 || ny >= M)
						break;
				}
			}
		}
		//4번
		else if (cctv[i].t == 4) {
			for (int d = 0; d <= 4; d += 2) {
				int nx = cctv[i].x + FourD[cctvDir[i]][d];
				int ny = cctv[i].y + FourD[cctvDir[i]][d + 1];
				//다른 cctv나 벽과 경계에 부딪히기 전까지
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;
				while (cMap[nx][ny] != 6) {
					cMap[nx][ny] = -1;
					nx += FourD[cctvDir[i]][d];
					ny += FourD[cctvDir[i]][d + 1];
					if (nx < 0 || nx >= N || ny < 0 || ny >= M)
						break;
				}
			}
		}
		//5번
		else if (cctv[i].t == 5) {
			for (int d = 0; d < 4; d++) {
				int nx = cctv[i].x + FiveD[d][0];
				int ny = cctv[i].y + FiveD[d][1];
				//다른 cctv나 벽과 경계에 부딪히기 전까지
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;
				while (cMap[nx][ny] != 6) {
					cMap[nx][ny] = -1;
					nx += FiveD[d][0];
					ny += FiveD[d][1];
					if (nx < 0 || nx >= N || ny < 0 || ny >= M)
						break;
				}
			}
		}
	}
}

void getDir(int cnt) {
	if (cnt == cctvCnt) {
		//감시구역 표시하고 사각지대 개수 세기
		markArea();
		int res = countArea();
		Min = min(Min, res);
		return;
	}
	//1번 cctv인 경우
	if (cctv[cnt].t == 1) {
		for (int i = 0; i < 4; i++) {
			cctvDir[cnt] = i;
			getDir(cnt + 1);
		}
	}
	//2번 cctv인 경우
	else if (cctv[cnt].t == 2) {
		for (int i = 0; i < 2; i++) {
			cctvDir[cnt] = i;
			getDir(cnt + 1);
		}
	}
	//3번 cctv인 경우
	else if (cctv[cnt].t == 3) {
		for (int i = 0; i < 4; i++) {
			cctvDir[cnt] = i;
			getDir(cnt + 1);
		}
	}
	//4번 cctv인 경우
	else if (cctv[cnt].t == 4) {
		for (int i = 0; i < 4; i++) {
			cctvDir[cnt] = i;
			getDir(cnt + 1);
		}
	}
	//5번 cctv인 경우
	else if (cctv[cnt].t == 5) {
		cctvDir[cnt] = 0;
		getDir(cnt + 1);
	}
}

void solution() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
			//cctv 저장
			if (Map[i][j] != 0 && Map[i][j] != 6) {
				cctv.push_back({ i,j,Map[i][j] });
				cctvCnt++;
			}
		}
	}
	//0번째 cctv부터 방향 정하기
	getDir(0);
	/*
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << cMap[i][j] << ' ';
		}
		cout << '\n';
	}*/
	cout << Min << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}