[BOJ 15683] 감시

문제출처

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

 

문제풀이

8대의 카메라가 4방향 모두 탐색하는 경우가 총 64개의 공간에서 일어날 수 있으므로 이 문제의 시간복잡도는 대략 4^8*64이므로 완전탐색으로 1초안에 풀이 가능하다.

입력을 받을때 cctv의 타입과 좌표를 따로 저장하고 dfs로 완전탐색해서 풀이했다. 처음에 어떻게 탐색을 해야하는지 고생을 했는데 1시간동안 탐색방법이 떠오르지 않아 na982님의 풀이를 확인하고 문제풀이를 했다. 그러다보니 na982님 풀이에 생각이 박혀서 다시 풀어도 같은 소스코드가 나왔다. 이 풀이에서 4방향 탐색을 할때 하나의 함수를 만들어 안에서 분기처리 하는 방법이 매우 마음에 들었다. 비록 이 문제는 내가 처음부터 끝까지 풀지는 못했으나 좋은 아이디어를 얻는 계기가 된듯 하다.

풀이방법은 https://na982.tistory.com/95 여기를 참조하자. 정말 잘 설명해주시는듯 ㅠㅠ

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct CCTV {
	int type, y, x;
};
int n, m, ans = 987654321;
const int rotateCount[] = { 4,2,4,4,1 };
int map[8][8];
vector<CCTV> cctv;
void init() {
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];
			if (map[y][x] != 0 && map[y][x] != 6) {
				cctv.push_back({ map[y][x], y, x });
			}
		}
	}
}
void copyMap(int src[8][8], int desc[8][8]) {
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			desc[y][x] = src[y][x];
		}
	}
}
void rotateCamera(int dir, CCTV cctv) {
	dir %= 4;

	if (dir == 0) {
		for (int x = cctv.x + 1; x < m; x++) {
			if (map[cctv.y][x] == 6) break;
			map[cctv.y][x] = -1;
		}
	} else if (dir == 1) {
		for (int y = cctv.y - 1; y >= 0; y--) {
			if (map[y][cctv.x] == 6) break;
			map[y][cctv.x] = -1;
		}
	} else if (dir == 2) {
		for (int x = cctv.x - 1; x >= 0; x--) {
			if (map[cctv.y][x] == 6) break;
			map[cctv.y][x] = -1;
		}
	} else if (dir == 3) {
		for (int y = cctv.y + 1; y < n; y++) {
			if (map[y][cctv.x] == 6) break;
			map[y][cctv.x] = -1;
		}
	}
}
void dfs(int index) {
	if (index == cctv.size()) {
		int safeArea = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) {
				if (map[y][x] == 0) safeArea++;
			}
		}
		ans = min(ans, safeArea);
		return;
	}
	int type = cctv[index].type;
	int backup[8][8] = { 0, };
	for (int i = 0; i < rotateCount[type-1]; i++) {
		copyMap(map, backup);
		if (type == 1) {
			rotateCamera(i, cctv[index]);
		} else if (type == 2) {
			rotateCamera(i, cctv[index]);
			rotateCamera(i + 2, cctv[index]);
		} else if (type == 3) {
			rotateCamera(i, cctv[index]);
			rotateCamera(i + 1, cctv[index]);
		} else if (type == 4) {
			rotateCamera(i, cctv[index]);
			rotateCamera(i + 1, cctv[index]);
			rotateCamera(i + 2, cctv[index]);
		} else if (type == 5) {
			rotateCamera(i, cctv[index]);
			rotateCamera(i + 1, cctv[index]);
			rotateCamera(i + 2, cctv[index]);
			rotateCamera(i + 3, cctv[index]);
		}
		dfs(index + 1);
		copyMap(backup, map);
	}

}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	dfs(0);
	cout << ans << "\n";
	return 0;
}