백준 15683 감시

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

15683번: 감시

 

- 역시나 브루트포스, 백트래킹 문제이다. 구현 난이도 자체는 어렵지 않다.

 

- 감시카메라의 좌표를 벡터에 담고, 해당 카메라가 가질 수 있는 모든 경우의 수에 대해 조사를 한다. 감시가 되는 구역을 선택할 때

  (1) 해당 구역이 벽이면 감시구역 조사를 중단한다.

  (2) 해당 구역이 0이면 감시구역(-1)임을 표시한다.

  (3) 해당 구역이 감시카메라이거나 이미 감시된 구역인 경우 continue한다.

 

- 또한, 각 재귀 호출마다 이전 상태로 돌아갈 temp1을 두고, 전역으로 temp2를 두어서 temp2는 마지막 사각지대 조사에 사용되도록 한다.

 

- 문제를 꼼꼼히 읽자. 감시카메라가 있는 부분을 벽이 있는 부분과 동일한 로직으로 처리하는 바람에 시간이 오래 걸렸다..

 

- 코드를 리팩토링하면 훨씬 더 깔끔하게 구현할 수 있을 것이다. 하지만 나는 구현에 목적을 두어서 하드코딩을 했다.(귀찮은 것도 한몫)

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m;
int answer = 100000000;
int map[8][8];
int temp2[8][8];
int num_of_camera;

void DFS(int cnt, vector<pair<int,int>>& v ) {
	int temp1[8][8];
	if (cnt == num_of_camera) {
		int temp_answer = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (temp2[i][j] == 0) temp_answer++;
			}
		}
		answer = min(answer, temp_answer);
		return;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			temp1[i][j] = temp2[i][j];
		}
	}
	int x = v[cnt].first;
	int y = v[cnt].second;
	int sort_of_camera = map[x][y];
	if (sort_of_camera == 1) {
		//상, 하, 좌, 우 4가지 case로 나누어 DFS진행
		for (int i = x-1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt+1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = y-1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = y+1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
	}
	else if (sort_of_camera == 2) { // 상,하 / 좌,우
		for (int i = x-1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = x+1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = y-1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = y+1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
	}
	else if (sort_of_camera == 3) { // 3번 카메라 - 상/우, 우/하, 하/좌, 좌/상
		for (int i = x-1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y+1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = y+1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y - 1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = y - 1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = x - 1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
	}
	else if (sort_of_camera == 4) { // 좌/상/우, 상/우/하, 우/하/좌, 하/좌/상
		for (int i = y - 1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = x - 1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y + 1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = x - 1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y + 1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = y + 1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y - 1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y - 1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = x - 1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
	}
	else if (sort_of_camera == 5) { // 상/하/좌/우
		for (int i = x - 1; i >= 0; i--) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = x + 1; i < n; i++) {
			if (temp2[i][y] == 6) break;
			else if (!temp2[i][y]) temp2[i][y] = -1;
			else continue;
		}
		for (int i = y - 1; i >= 0; i--) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		for (int i = y + 1; i < m; i++) {
			if (temp2[x][i] == 6) break;
			else if (!temp2[x][i]) temp2[x][i] = -1;
			else continue;
		}
		DFS(cnt + 1, v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp2[i][j] = temp1[i][j];
			}
		}
	}
}
int main() {
	cin >> n >> m;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0 && map[i][j] != 6) {
				v.push_back({ i,j });
			}
			temp2[i][j] = map[i][j];
		}
	}
	num_of_camera = v.size();
	DFS(0, v);
	cout << answer << '\n';
	return 0;
}