728x90
반응형
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
struct CCTV{
int x;
int y;
int num;
int dir;
};
int n, m, answer = 2e9;
int MAP[9][9];
int CMAP[9][9];
vector<CCTV> cctv;
void input(){
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int tmp;
cin >> tmp;
MAP[i][j] = tmp;
if(tmp>0 && tmp<6) cctv.push_back({i, j, tmp, -1});
}
}
}
void copyMap(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
CMAP[i][j] = MAP[i][j];
}
}
}
void right(int x, int y){
for(int i=y+1; i<m; i++){
if(CMAP[x][i]==6)
break;
else if(CMAP[x][i]>=1 && CMAP[x][i]<=6)
continue;
else
CMAP[x][i] =-1;
}
}
void left(int x, int y){
for(int i=y-1; i>=0; i--){
if(CMAP[x][i]==6)
break;
else if(CMAP[x][i]>=1 && CMAP[x][i]<=6)
continue;
else
CMAP[x][i] = -1;
}
}
void up(int x, int y){
for(int i=x-1; i>=0; i--){
if(CMAP[i][y]==6)
break;
else if(CMAP[i][y]>=1 && CMAP[i][y]<=5)
continue;
else
CMAP[i][y] = -1;
}
}
void down(int x, int y){
for(int i=x+1; i<n; i++){
if(CMAP[i][y]==6)
break;
else if(CMAP[i][y]>=1 && CMAP[i][y]<=5)
continue;
else
CMAP[i][y] = -1;
}
}
void checkArea(){
copyMap();
for(int i=0; i<cctv.size(); i++){
if(cctv[i].num == 1){ // 1번 cctv인 경우
if(cctv[i].dir == 0) right(cctv[i].x, cctv[i].y);
else if(cctv[i].dir == 1) left(cctv[i].x, cctv[i].y);
else if(cctv[i].dir == 2) up(cctv[i].x, cctv[i].y);
else if(cctv[i].dir == 3) down(cctv[i].x, cctv[i].y);
} else if(cctv[i].num == 2) { // 2번 cctv인 경우
if(cctv[i].dir == 0 || cctv[i].dir == 2) {
right(cctv[i].x, cctv[i].y);
left(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 1 || cctv[i].dir == 3) {
up(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
}
} else if(cctv[i].num == 3) { // 3번 cctv인 경우
if(cctv[i].dir == 0) {
up(cctv[i].x, cctv[i].y);
right(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 1){
up(cctv[i].x, cctv[i].y);
left(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 2) {
left(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 3) {
right(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
}
} else if(cctv[i].num == 4) { // 4번 cctv인 경우
if(cctv[i].dir == 0) {
left(cctv[i].x, cctv[i].y);
up(cctv[i].x, cctv[i].y);
right(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 1){
up(cctv[i].x, cctv[i].y);
left(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 2) {
left(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
right(cctv[i].x, cctv[i].y);
} else if(cctv[i].dir == 3) {
up(cctv[i].x, cctv[i].y);
right(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
}
} else if(cctv[i].num == 5) { // 5번 cctv인 경우
up(cctv[i].x, cctv[i].y);
right(cctv[i].x, cctv[i].y);
down(cctv[i].x, cctv[i].y);
left(cctv[i].x, cctv[i].y);
}
}
}
int numOfSecretArea(){
int sum = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(CMAP[i][j]==0) sum++;
}
}
return sum;
}
void setCctvDir(int cnt){
if(cnt == cctv.size()){
checkArea();
answer = min(answer, numOfSecretArea());
return;
}
cctv[cnt].dir = 0;
setCctvDir(cnt+1);
cctv[cnt].dir = 1;
setCctvDir(cnt+1);
cctv[cnt].dir = 2;
setCctvDir(cnt+1);
cctv[cnt].dir = 3;
setCctvDir(cnt+1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
setCctvDir(0);
cout << answer;
return 0;
}
참고
728x90
반응형
'알고리즘 > 완전탐색(블루트포스)' 카테고리의 다른 글
| [백준/완전탐색/C++] 4375번 1 * (0) | 2023.01.15 |
|---|