[C++] 백준 15683번: 감시

www.acmicpc.net/problem/15683

15683번: 감시

처음에 단순히 각각의 최대값들만 계산하게 구현했다가 안되서 한동안 코테 공부를 소홀하게 만든 문제이다..

 

단순 구현 문제임에도 고려해야 될 사항들이 많은 문제라 많이 어려웠다.(내 생각엔 최악의 문제이다..ㅠㅠ)

 

고민하다가 결국 재귀로 해결할 수 있었고 모든 경우의 수를 브루트 포스와 비슷하게 다 고려하여 풀었다.

 

각 cctv의 시야 범위를 7로 바꾸는 부분은 바킹독님의 풀이를 참고하여 수정하였다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, ans = 987654;

int map2[10][10];
int cam2[2][2] = { {1,3},{2,4} };
int cam3[4][2] = { {1,2},{2,3},{3,4},{1,4} };
int cam4[4][3] = { {1,2,3},{2,3,4},{1,3,4},{1,2,4} };
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1,0 };
vector<pair<int, int>> v;


void cpy(int(*map1)[10]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map2[i][j] = map1[i][j];
		}
	}
}

void cpy2(int (*map1)[10]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map1[i][j] = map2[i][j];
		}
	}
}

void check(int x, int y, int dir) {
	while (1) {
		x += dx[dir-1];
		y += dy[dir-1];
		if (x < 0 || y < 0 || x >= N || y >= M || map2[x][y] == 6) {
			return;
		}
		if (map2[x][y] != 0) {
			continue;
		}
		map2[x][y] = 7;
	}
}

void dfs(int cnt) {
	int map1[10][10];
	cpy2(map1);
	if (cnt == v.size()) {
		int k = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map2[i][j] == 0) {
					k++;
				}
			}
		}
		ans = min(ans, k);
		return;
	}
	
	int x = v[cnt].first;
	int y = v[cnt].second;
	if (map2[x][y] == 1) {
		for (int i = 1; i <= 4; i++) {
			cpy2(map1);
			check(x, y, i);
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 2) {
		for (int i = 0; i < 2; i++) {
			cpy2(map1);
			for (int j = 0; j < 2; j++) {
				check(x, y, cam2[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 3) {
		for (int i = 0; i < 4; i++) {
			cpy2(map1);
			for (int j = 0; j < 2; j++) {
				check(x, y, cam3[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 4) {
		cpy2(map1);
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 3; j++) {
				check(x, y, cam4[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else {
		cpy2(map1);
		for (int i = 1; i <= 4; i++) {
			check(x, y, i);
		}
		cnt++;
		dfs(cnt);
		cnt--;
		cpy(map1);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map2[i][j];
			if (map2[i][j] != 0 && map2[i][j] != 6) {
				v.push_back({ i,j });
			}
		}
	}
	dfs(0);
	
	cout << ans;
}