#15683 감시

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

15683번: 감시

 

풀이

dfs + 시뮬레이션 문제

먼저 cctv의 개수를 vector에 보관한 후 dfs를 통해 각 cctv별 어떤 방향으로 감시를 할 것인지에 대해 기록한다. 그렇게 방향 정보를 다 기록하고 나면 map을 채우게 되는데 이때 fill_map함수를 실행하여 cctv 번호마다 어떤식으로 감시하는지를 표현하였다. 그리고 그 안에서 simul이라는 함수가 실행되는데 simul함수는 해당 cctv위치를 기준으로 d방향만큼 일직선으로 맵을 채워주는 함수이다.

 

코드

 

 

	// #15683 감시 10:24
	//k개의 cctv 종류는 5가지
	// 6이 벽 , cctv: 1~5번
	//사각지대 최소 크기는? cctv의 최대개수는 8개를 넘지 않음
	//cctv끼리는 통과 가능
	//cctv개수 저장하고 4방향만큼 계속 돌려가면서 cctv방향 정해주는 dfs함수
	//map 채워주는 함수
	#include <iostream>
	#include <cstring>
	#include <algorithm>
	#include <vector>
	#define INF 100000000
	using namespace std;
	int ans = INF;
	int n, m;
	int dir[4][2] = { {0,1}, { 1,0 }, { 0,-1 }, { -1,0 } };//우,하,좌,상
	int map[9][9];
	int visit[9][9];
	typedef struct info {
	int x, y;
	int cctvnum;
	};
	vector <info> cctv;
	int svisit[9];
	int cctvsz;
	void simul(int x,int y,int d) {
	while (true) {
	visit[x][y] = 7;
	x += dir[d][0], y += dir[d][1];
	if (x < 0 || y < 0 || x >= n || y >= m)return;
	if (map[x][y] == 6)return;
	}
	}
	void fill_map(int order) {
	int d = svisit[order];
	int fx = cctv[order].x, fy = cctv[order].y;
	int cctvnum = cctv[order].cctvnum;
	if (cctvnum == 1) {
	simul(fx, fy, d);
	}
	else if (cctvnum == 2) {
	simul(fx, fy, d);
	simul(fx, fy, (d+2)%4);
	}
	else if (cctvnum == 3) {
	simul(fx, fy, d);
	simul(fx, fy, (d + 1) % 4);
	}
	else if (cctvnum == 4) {
	simul(fx, fy, d);
	simul(fx, fy, (d + 1) % 4);
	simul(fx, fy, (d + 2) % 4);
	}
	else if (cctvnum == 5) {
	simul(fx, fy, d);
	simul(fx, fy, (d + 1) % 4);
	simul(fx, fy, (d + 2) % 4);
	simul(fx, fy, (d + 3) % 4);
	}
	}
	void dfs(int cnt) {
	//if cnt==cctv.size()
	if (cnt == cctvsz) {
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < cctvsz; i++) {
	fill_map(i);
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (visit[i][j] == 0 && map[i][j] != 6)sum++;
	}
	}
	ans = min(ans, sum);
	return;
	}
	// 0000, 0001, 0002, 0003, 이런식으로 돌려가고
	for (int d = 0; d < 4; d++) {
	svisit[cnt] = d;
	dfs(cnt + 1);
	}
	}
	int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	cin >> map[i][j];
	if (map[i][j] >= 1 && map[i][j] <= 5) {
	cctv.push_back({ i,j,map[i][j] });
	}
	}
	}
	cctvsz = cctv.size();
	dfs(0);
	cout << ans << endl;
	}

view raw [BOJ]15683 감시.cpp hosted with ❤ by GitHub