문제풀이/백준oj
[백준OJ] 15683번 감시
Hyeon-Uk
2021. 4. 26. 20:59
반응형
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
-풀이-
입력받을 때, cctv들은 모두 벡터에 넣어둔 뒤, 백트래킹을 이용하여 , 모든 cctv들이 감시할 수 있는 상황을 구해주고, 최소 사각지대를 업데이트 해준다.
이때 아래 함수들로 인해, 입력받은 배열들을 모두 음수로 바꿔준다.
paint함수: 원하는 방향에 따라 감시카메라기준 해당방향으로 표시를 해준다. 이때 백트래킹을 할때 다른 cctv로인해 지워지지 않게, 현재 cctv인덱스+1로 표시 해준다.
void paint(int x,int y,int d,int cnt){
if(d==0){
for(int i=x-1;i>=0;i--){
if(maze[i][y]==-6) break;
if(maze[i][y]==0) maze[i][y]=cnt+1;
}
}
else if(d==1){
for(int i=y+1;i<m;i++){
if(maze[x][i]==-6) break;
if(maze[x][i]==0) maze[x][i]=cnt+1;
}
}
else if(d==2){
for(int i=x+1;i<n;i++){
if(maze[i][y]==-6) break;
if(maze[i][y]==0) maze[i][y]=cnt+1;
}
}
else{
for(int i=y-1;i>=0;i--){
if(maze[x][i]==-6) break;
if(maze[x][i]==0) maze[x][i]=cnt+1;
}
}
}
remove_paint함수:
백트래킹을 할때, 해당 cctv가 볼 수 있는 범위라고 표시한것만 지워주는 함수이다.
void remove_paint(int x,int y,int d,int cnt){
if(d==0){
for(int i=x-1;i>=0;i--){
if(maze[i][y]==-6) break;
if(maze[i][y]==cnt+1) maze[i][y]=0;
}
}
else if(d==1){
for(int i=y+1;i<m;i++){
if(maze[x][i]==-6) break;
if(maze[x][i]==cnt+1) maze[x][i]=0;
}
}
else if(d==2){
for(int i=x+1;i<n;i++){
if(maze[i][y]==-6) break;
if(maze[i][y]==cnt+1) maze[i][y]=0;
}
}
else{
for(int i=y-1;i>=0;i--){
if(maze[x][i]==-6) break;
if(maze[x][i]==cnt+1) maze[x][i]=0;
}
}
}
dfs함수:
모든 경우의수를 만들어주는 백트래킹 함수. 각각의 경우의수마다 사각지대의 개수를 카운팅하여 업데이트 해준다.
void dfs(int now){
if(now==cctv.size()){
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(maze[i][j]==0) cnt++;
}
}
result=min(result,cnt);
return;
}
int number=cctv[now].second;
int x=cctv[now].first.first;
int y=cctv[now].first.second;
if(number==1){
for(int i=0;i<4;i++){
paint(x,y,i,now);
dfs(now+1);
remove_paint(x,y,i,now);
}
}
else if(number==2){
for(int i=0;i<2;i++){
paint(x,y,i,now);
paint(x,y,i+2,now);
dfs(now+1);
remove_paint(x,y,i,now);
remove_paint(x,y,i+2,now);
}
}
else if(number==3){
paint(x,y,0,now);
for(int i=0;i<4;i++){
paint(x,y,(i+1)%4,now);
dfs(now+1);
remove_paint(x,y,i,now);
}
remove_paint(x,y,0,now);
}
else if(number==4){
paint(x,y,0,now);
paint(x,y,1,now);
for(int i=0;i<4;i++){
paint(x,y,(i+2)%4,now);
dfs(now+1);
remove_paint(x,y,i,now);
}
remove_paint(x,y,0,now);
remove_paint(x,y,1,now);
}
else{
for(int i=0;i<4;i++){
paint(x,y,i,now);
}
dfs(now+1);
for(int i=0;i<4;i++){
remove_paint(x,y,i,now);
}
}
}
-시간복잡도-
cctv하나가 최대 4가지의 경우가 나오므로, 최악의 경우는 총 O(4^K) , K는 cctv개수가 된다. 하지만 K<=8이므로 시간안에 충분히 들어온다.
-코드-
#include<iostream>
#include<algorithm>
using namespace std;
int maze[8][8];
int n,m,result=64;
vector<pair<pair<int,int>,int>> cctv;
//d=0 위, d=1 오,d=2 아, d=3 왼
void paint(int x,int y,int d,int cnt){
if(d==0){
for(int i=x-1;i>=0;i--){
if(maze[i][y]==-6) break;
if(maze[i][y]==0) maze[i][y]=cnt+1;
}
}
else if(d==1){
for(int i=y+1;i<m;i++){
if(maze[x][i]==-6) break;
if(maze[x][i]==0) maze[x][i]=cnt+1;
}
}
else if(d==2){
for(int i=x+1;i<n;i++){
if(maze[i][y]==-6) break;
if(maze[i][y]==0) maze[i][y]=cnt+1;
}
}
else{
for(int i=y-1;i>=0;i--){
if(maze[x][i]==-6) break;
if(maze[x][i]==0) maze[x][i]=cnt+1;
}
}
}
void remove_paint(int x,int y,int d,int cnt){
if(d==0){
for(int i=x-1;i>=0;i--){
if(maze[i][y]==-6) break;
if(maze[i][y]==cnt+1) maze[i][y]=0;
}
}
else if(d==1){
for(int i=y+1;i<m;i++){
if(maze[x][i]==-6) break;
if(maze[x][i]==cnt+1) maze[x][i]=0;
}
}
else if(d==2){
for(int i=x+1;i<n;i++){
if(maze[i][y]==-6) break;
if(maze[i][y]==cnt+1) maze[i][y]=0;
}
}
else{
for(int i=y-1;i>=0;i--){
if(maze[x][i]==-6) break;
if(maze[x][i]==cnt+1) maze[x][i]=0;
}
}
}
void dfs(int now){
if(now==cctv.size()){
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(maze[i][j]==0) cnt++;
}
}
result=min(result,cnt);
return;
}
int number=cctv[now].second;
int x=cctv[now].first.first;
int y=cctv[now].first.second;
if(number==1){
for(int i=0;i<4;i++){
paint(x,y,i,now);
dfs(now+1);
remove_paint(x,y,i,now);
}
}
else if(number==2){
for(int i=0;i<2;i++){
paint(x,y,i,now);
paint(x,y,i+2,now);
dfs(now+1);
remove_paint(x,y,i,now);
remove_paint(x,y,i+2,now);
}
}
else if(number==3){
paint(x,y,0,now);
for(int i=0;i<4;i++){
paint(x,y,(i+1)%4,now);
dfs(now+1);
remove_paint(x,y,i,now);
}
remove_paint(x,y,0,now);
}
else if(number==4){
paint(x,y,0,now);
paint(x,y,1,now);
for(int i=0;i<4;i++){
paint(x,y,(i+2)%4,now);
dfs(now+1);
remove_paint(x,y,i,now);
}
remove_paint(x,y,0,now);
remove_paint(x,y,1,now);
}
else{
for(int i=0;i<4;i++){
paint(x,y,i,now);
}
dfs(now+1);
for(int i=0;i<4;i++){
remove_paint(x,y,i,now);
}
}
}
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>>maze[i][j];
if(maze[i][j]!=0&&maze[i][j]!=6){
cctv.push_back({{i,j},maze[i][j]});
maze[i][j]=-maze[i][j];
}
else if(maze[i][j]==6){
maze[i][j]=-6;
}
}
}
dfs(0);
cout<<result<<"\n";
return 0;
}
반응형