<Baekjoon> #15683 DFS, Backtracking, Brute Force_감시 c++

#15683 감시
참고1

💬문제설명 및 아이디어

• 각 cctv는 감시할 수 있는 영역이 다르다.
  1번 cctv를 예로 들면 오른쪽 방향만 감시할 수 있다는 의미가 아니라 한 방향으로만 감시할 수 있다는 뜻이다.
  따라서 1번 cctv가 나왔을 경우, 동서남북 방향으로 모두 감시 해보고 어느 방향으로 감시했을 때가 최적의 방법인지 찾아야한다.
  
• 그림과 같이 각각의 cctv는 {4,2,4,4,1}가지의 방향을 가지고 있으며 이 경우를 모두 탐색해주어야 한다
• cctv는 벽을 통과할 수는 없지만 cctv를 통과할 수 있다

👩‍💻1. input Data

• 사무실에 있는 벽과 cctv에 관한 정보를 입력받을 때, cctv는 vector<CCTV> cctv에 저장해준다. struct CCTV에는 cctv의 (y,x)좌표와 cctv의 번호가 저장된다.

struct CCTV {
	int y, x, idx;
};
vector<CCTV> cctv;

for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		cin >> office[i][j];
		if (office[i][j] >= 1 && office[i][j] <= 5)
			cctv.push_back({ i, j, office[i][j] });
	}
}

👩‍💻2. 각 방향으로의 감시

• 위에서 나타냈던 각 cctv의 모든 방향을 따로 정의하지 않고 감시할 방향 d를 인자로 보내면 d에 따라 동(0)서(1)남(2)북(3)으로 감시한다.
  예를 들어 5번 cctv가 있을 경우, 동서남북 방향으로 4번 함수를 호출한다.
• vector<vector<int>> inspectArea(vector<vector<int>> tmp, int d, int r, int c)
  ① tmp: 현재 사무실의 상태를 담은 이차원 벡터
  ② d: 감시할 방향
  ③ (r,c): 현재 cctv의 좌표
• 동쪽(0)방향으로의 감시만 예로 들어보면, y좌표는 변함이 없고 x좌표가 사무실을 벗어나지 않고 벽이 아닐 때까지 감시한다

if (d == 0) {
	int j = c + 1;
	while (j < M && tmp[r][j] != WALL) {
		tmp[r][j++] = INSPECT;
	}
}

👩‍💻3. dfs 함수 구현

• void dfs(int L, vector<vector<int>> office)
L은 cctv의 갯수와 같아질 때까지 반복하다가 같아지면office에서 빈 공간의 갯수를 구하여 최솟값을 갱신한다

if (L == cctv.size()) {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (office[i][j] == EMPTY)
				cnt++;
		}
	}
	minCnt = min(minCnt, cnt);
	return;
}

• L번째 cctv의 정보를 보고 cIdx즉, 어떤 cctv냐에 따라서 cctv가 감시해야 하는 영역을 탐색한다

	int cy = cctv[L].y;
	int cx = cctv[L].x;
	int cIdx = cctv[L].idx;

• 가장 복잡한 4번 cctv를 예로 들어보자
  

else if (cIdx == 4) {
	for (int i = 0; i < 4; i++) {
		tmp = office;
		for (int j = 0; j < 4; j++) {
			if (i == j) continue;
			tmp = inspectArea(tmp, j, cy, cx);
		}
		dfs(L + 1, tmp);
	}
}

총 4번 각각 다른 모양을 만들어야하고, 각 모양마다 3방향이 있기 때문에 3번 inspectArea를 호출해서 현재 사무실의 상태를 담은 tmp를 다시 재귀호출한다.

전체코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int EMPTY = 0;
const int WALL = 6;
const int INSPECT = -1;
int minCnt = 64;
int N, M;

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

struct CCTV {
	int y, x, idx;
};
vector<CCTV> cctv;

vector<vector<int>> inspectArea(vector<vector<int>> tmp, int d, int r, int c) {
	if (d == 0) {
		int j = c + 1;
		while (j < M && tmp[r][j] != WALL) {
			tmp[r][j++] = INSPECT;
		}
	}
	else if (d == 1) {
		int j = c - 1;
		while (j >= 0 && tmp[r][j] != WALL) {
			tmp[r][j--] = INSPECT;
		}
	}
	else if (d == 2) {
		int i = r + 1;
		while (i < N && tmp[i][c] != WALL) {
			tmp[i++][c] = INSPECT;
		}
	}
	else if (d == 3) {
		int i = r -1;
		while (i>=0 && tmp[i][c] != WALL) {
			tmp[i--][c] = INSPECT;
		}
	}
	return tmp;
}

void dfs(int L, vector<vector<int>> office) {
	if (L == cctv.size()) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (office[i][j] == EMPTY)
					cnt++;
			}
		}
		minCnt = min(minCnt, cnt);
		return;
	}
 
	vector<vector<int>>tmp;

	int cy = cctv[L].y;
	int cx = cctv[L].x;
	int cIdx = cctv[L].idx;

	if (cIdx == 1) {
		for (int i = 0; i < 4; i++) {
			dfs(L + 1, inspectArea(office, i, cy, cx));
		}
	}

	else if (cIdx == 2) {
		tmp = inspectArea(office, 0, cy, cx);
		tmp = inspectArea(tmp, 1, cy, cx);
		dfs(L + 1, tmp);
		tmp = inspectArea(office, 2, cy, cx);
		tmp = inspectArea(tmp, 3, cy, cx);
		dfs(L + 1, tmp);
	}

	else if (cIdx == 3) {
		tmp = inspectArea(office, 0, cy, cx);
		tmp = inspectArea(tmp, 3, cy, cx);
		dfs(L + 1, tmp);

		tmp = inspectArea(office, 2, cy, cx);
		tmp = inspectArea(tmp, 1, cy, cx);
		dfs(L + 1, tmp);

		tmp = inspectArea(office, 1, cy, cx);
		tmp = inspectArea(tmp, 3, cy, cx);
		dfs(L + 1, tmp);

		tmp = inspectArea(office, 0, cy, cx);
		tmp = inspectArea(tmp, 2, cy, cx);
		dfs(L + 1, tmp);
	}
	
	else if (cIdx == 4) {
		for (int i = 0; i < 4; i++) {
			tmp = office;
			for (int j = 0; j < 4; j++) {
				if (i == j) continue;
				tmp = inspectArea(tmp, j, cy, cx);
			}
			dfs(L + 1, tmp);
		}
	}

	else if (cIdx == 5) {
		tmp = office;
		for (int i = 0; i < 4; i++)
			tmp = inspectArea(tmp, i, cy, cx);
		dfs(L + 1, tmp);
	}
}

void input() {
	cin >> N >> M;
	vector<vector<int>> office = vector<vector<int>>(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> office[i][j];
			if (office[i][j] >= 1 && office[i][j] <= 5)
				cctv.push_back({ i, j, office[i][j] });
		}
	}
	dfs(0, office);
}

int main() {
	input();
	cout << minCnt << endl;

	return 0;
}