15683 감시
코드 설명
CCTV의 종류를 입력받은후 각각의 가지수를 전부 카운트 해보는 문제이다. 문제에 들어가기전 완전탐색이 맞는지 시간초과가 안날지 최악의case를 먼저 계산해보는 습관을 가지자
4^8 * 64 이므로 대략 400만정도이므로 1초 안에 가능하다.
그다음에는 각 CCTV마다 탐색할수있는 방향의 개수를 담은 배열을 만들자(편함!)
rotate_arr[]={4,2,4,4,1};
이건 완전탐색에서 type별 branch 개수가 된다
find()함수를 만들어서 한 방향을 매개변수로 받고 그 방향에서 벽을 만나기전까지 전부 탐색한다(#)
방향만큼 함수를 호출한다(코드주석참고)
코드
#include<iostream>
#include<vector>
using namespace std;
struct CCTV {
int type; //0,1,2,3
int y;
int x;
};
CCTV cctv[8];
int map[8][8];
int answer = 1000;
int N, M;
int K; //CCTV 개수
int rotate_arr[] = { 4,2,4,4,1 }; //type별 총 회전가능 횟수
void find(int dir, CCTV cctv) { // 한방향 모두 탐색하는 함수
dir = dir % 4;
if (dir == 0) {//동쪽 끝까지
for (int i = cctv.x + 1; i < M; i++) {
if (map[cctv.y][i] == 6) break;
map[cctv.y][i] = -1; //-1로 탐색 완료 표시 (#)
}
}
if (dir == 1) { //북쪽
for (int i = cctv.y - 1; i >= 0; i--) {
if (map[i][cctv.x] == 6) break;
map[i][cctv.x] = -1;
}
}
if (dir == 2) { //서쪽
for (int i = cctv.x - 1; i >= 0; i--) {
if (map[cctv.y][i] == 6) break;
map[cctv.y][i] = -1;
}
}
if (dir == 3) { //남쪽
for (int i = cctv.y + 1; i < N; i++) {
if (map[i][cctv.x] == 6) break;
map[i][cctv.x] = -1;
}
}
}
void dfs(int level) {
if (level == K) {
int cnt = 0;//사각지대크기 count
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
if (map[y][x] == 0) cnt++;
}
}
answer = min(answer, cnt);
return;
}
int backup[8][8];
int type = cctv[level].type;
for (int i = 0; i < rotate_arr[type]; i++) { //각 cctv type별로 탐색
memcpy(backup, map, sizeof(map)); //map을 backup복사
if (type == 0) { //한방향만 탐색
find(i, cctv[level]);
}
else if (type == 1) {//두방향탐색
find(i, cctv[level]);
find(i+2, cctv[level]);
}
else if (type == 2) { //두방향
find(i, cctv[level]);
find(i+1, cctv[level]);
}
else if (type == 3) { //세방향
find(i, cctv[level]);
find(i + 1, cctv[level]);
find(i + 2, cctv[level]);
}
else if (type == 4) { //네방향
find(i, cctv[level]);
find(i + 1, cctv[level]);
find(i + 2, cctv[level]);
find(i + 3, cctv[level]);
}
dfs(level + 1);
memcpy(map, backup, sizeof(backup)); //탐색완료후 backup-> map복사 (완전탐색을 위해 한단계 탐색이후 돌아올때 그전 map상태 저장)
}
}
int main() {
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[K].y = y;
cctv[K].x = x;
cctv[K].type = map[y][x] - 1;
K++;
}
}
}
dfs(0);
cout << answer;
return 0;
}
Author And Source
이 문제에 관하여(15683 감시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@trevor522/15683-감시저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)