문제
삼성 문제다.
cctv가 5가지 방향에 맞춰 감시를 할때 사각지대의 최소화 값을 구하는 문제다.
문제 접근
일단 dfs로 풀어야하는게 명확했다.
문제는 깊이가 얼마나 될까 계산해보니 cctv마다 체크해야하는 유형이 달라서 고민이었다.
예를 들어 1번 cctv는 4방향 모두를 고려해야하는데 2번은 (좌우,상하) 2개만 고려하면 된다.
즉 1번부터 cctv의 경우의 수는 4,2,4,4,1가지이다.(트리 형태로 만들면 가지가 1~4개다.)
트리에서 노드마다 가지수가 다르다는건 각 타입마다 어떻게 진행해야할지를 각각 구현해줘야한다는 뜻이다.
coloring
cctv에 감시하는걸 coloring이라고하면(색칠하는거라고 생각했다) 진행 순서는 다음과 같다.
// coloring
// dfs
// uncoloring그리고 coloring을 할때 각 cctv마다 진행 방향이 다르니 한 방향으로만 진행하는것을
coloringOne으로 정했다.
예를 들어 1번 cctv는 coloringOne을 한번만 2번은 2번, 5번은 4번을 해야한다.
또한 coloring을 할때 어느방향으로 진행할지를 colorType으로 정했다.(4,2,4,4,1 경의 수)
그래서 2번 cctv는 2가지 경우만 있기에 colorType 3,4는 pass하면된다.
uncoloring
uncoloring은 coloring을 반대로 진행하면 된다.
문제는 uncoloring을 할때 자기가 색칠한것만 지워야한다는 것이다.
cctv가 중복해서 감시하는 경우가 생기는데 지울때 남이 감시하는것도 지워버리면 안된다.
이 문제는 2가지 해결방법이 떠올랐다.
1. graph를 하드카피해서 전체 상태를 저장.
2. coloring 횟수를 저장해서 카운트만 증가 및 감소.
1번으로 구현하는게 더 쉬울듯하다. 문제는 시간복잡도다. NM 연산을 매 단계마다 진행해줘야한다.
안그래도 현재 시간복잡도는 cctv 갯수를 K개로 했을때 매번 4가지 경우가 생기니 4^k인데 여기에 NM을 곱연산해주면 너무 느릴게 뻔했다.(k는 8이하)
그래서 2번으로 해결해줬다. coloring할때 -연산을 해주고 나중에 uncoloring할때 +을 해줘도 전체 -횟수만큼 증가해줘서 원래상태로 되돌릴 수 있었다.
느낀점
시뮬레이션 문제들의 핵심은 수도 코드로 작성할수있을만큼 정확한 절차를 짤수있는지 같다. 단순한 dfs,bfs를 사용할줄 아는지보다는 문제를 정확히 이해하고 복잡한 구현을 최대한 간단하게 구현하는게 중요할거같다.
code
/**
* 백준 15683
* 시뮬레이션
*/
#include <bits/stdc++.h>
using namespace std;
int N,M;
int graph[8][8];
vector<vector<int>> cctvs;
int maxNum=0;
int remain=0;
int cctvTypeNum[]={4,2,4,4,1};
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int coloringOne(int cctvIdx,int direction){
int y=cctvs[cctvIdx][0];
int x=cctvs[cctvIdx][1];
int ret=0;
while(true){
y+=dy[direction];
x+=dx[direction];
if(y<0||y>=N||x<0||x>=M) break;
if(graph[y][x]==6) break;
if(graph[y][x]==0) ret++;
if(graph[y][x]<=0) {
graph[y][x]--;
}
}
return ret;
}
int coloring(int cctvIdx,int colorType){
int ret=0;
int cctvType=cctvs[cctvIdx][2];
// type 1
if(cctvType==1){
ret+=coloringOne(cctvIdx,colorType);
}
// type 2
else if(cctvType==2){
if(colorType==0){
// 좌우
ret+=coloringOne(cctvIdx,1);
ret+=coloringOne(cctvIdx,3);
}
else if (colorType==1){
// 상하
ret+=coloringOne(cctvIdx,0);
ret+=coloringOne(cctvIdx,2);
}
else{
// 2,3은 pass
ret=-1;
}
}
// type 3
else if(cctvType==3){
ret+=coloringOne(cctvIdx,colorType);
ret+=coloringOne(cctvIdx,(colorType+1)%4);
}
// type 4
else if(cctvType==4){
ret+=coloringOne(cctvIdx,colorType);
ret+=coloringOne(cctvIdx,(colorType+1)%4);
ret+=coloringOne(cctvIdx,(colorType+2)%4);
}
// type 5
else if(cctvType==5){
if(colorType==0){
ret+=coloringOne(cctvIdx,colorType);
ret+=coloringOne(cctvIdx,(colorType+1)%4);
ret+=coloringOne(cctvIdx,(colorType+2)%4);
ret+=coloringOne(cctvIdx,(colorType+3)%4);
}
else ret=-1;
}
return ret;
}
void uncoloringOne(int cctvIdx,int direction){
int y=cctvs[cctvIdx][0];
int x=cctvs[cctvIdx][1];
while(true){
y+=dy[direction];
x+=dx[direction];
if(y<0||y>=N||x<0||x>=M) break;
if(graph[y][x]==6) break;
if(graph[y][x]<0){
graph[y][x]++;
}
}
}
void uncoloring(int cctvIdx,int colorType){
int cctvType=cctvs[cctvIdx][2];
// type 1
if(cctvType==1){
uncoloringOne(cctvIdx,colorType);
}
// type 2
else if(cctvType==2){
if(colorType==0){
// 좌우
uncoloringOne(cctvIdx,1);
uncoloringOne(cctvIdx,3);
}
else if (colorType==1){
// 상하
uncoloringOne(cctvIdx,0);
uncoloringOne(cctvIdx,2);
}
// 2,3은 pass
}
// type 3
else if(cctvType==3){
uncoloringOne(cctvIdx,colorType);
uncoloringOne(cctvIdx,(colorType+1)%4);
}
// type 4
else if(cctvType==4){
uncoloringOne(cctvIdx,colorType);
uncoloringOne(cctvIdx,(colorType+1)%4);
uncoloringOne(cctvIdx,(colorType+2)%4);
}
// type 5
else if(cctvType==5){
if(colorType==0){
uncoloringOne(cctvIdx,colorType);
uncoloringOne(cctvIdx,(colorType+1)%4);
uncoloringOne(cctvIdx,(colorType+2)%4);
uncoloringOne(cctvIdx,(colorType+3)%4);
}
}
}
void dfs(int cctvIdx,int sum){
if(cctvIdx>=cctvs.size()){
/*
//디버깅용
if(sum>maxNum){
std::cout<<"#### ans :"<<remain-sum<<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
std::cout<<graph[i][j]<<" ";
}
std::cout<<endl;
}
}
*/
maxNum=(sum>maxNum)?sum:maxNum;
return;
}
for(int colorType=0;colorType<4;colorType++){
int tmp=coloring(cctvIdx,colorType);
if(tmp!=-1) dfs(cctvIdx+1,sum+tmp);
uncoloring(cctvIdx,colorType);
}
}
int main(void){
cin>>N>>M;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
scanf("%d",&graph[i][j]);
if(graph[i][j]>0 && graph[i][j]<6){
cctvs.push_back({i,j,graph[i][j]});
}
if(graph[i][j]==0) remain++;
}
}
int sum=0;
if(!cctvs.empty()){
int startIdx=0;
for(int colorType=0;colorType<4;colorType++){
// coloring(영역 반환)
sum=coloring(startIdx,colorType);
if(sum!=-1) dfs(startIdx+1,sum);
// uncoloring
uncoloring(startIdx,colorType);
}
}
int ans=remain-maxNum;
std::cout<<ans<<endl;
}