[백준 15683][완전탐색][C++] 감시

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

15683번: 감시

구현이 생각보다 좀 빡센(...) 문제였는데, 군생활때문에 너무 오랜만에(거의 반반년만에) 코딩을 해서 더 심했던 것 같습니다.

 

cctv가 감시한 곳을 visited에 체크하면서 감시된 지역의 수를 세는 쪽으로 풀이의 방향을 잡았습니다. 그래서 먼저 각 cctv의 각각의 방향에 대한 감시할 수 있는 방향(말이 난잡하네요..)을 구할 벡터를 만들었습니다.

 

cctv에는 5가지 종류가 있는데, 각 cctv 방향의 경우의 수는 4,2,4,2,1으로 그렇게 많지 않아 3중벡터에 거의 하드코딩으로 직접 입력했습니다. 배열로 생각하면 pair<int,int> 자료형을 가진 array[a][b][c] 꼴이 될 수 있는데, 제 코드에서는 a는 cctv의 종류, b는 cctv의 방향, c는 그 방향에서 볼 수 있는 방향(예를 들어, 2번 카메라의 경우 서로 상반된 두 방향)을 나타냅니다.

 

입력을 받을 때 cctv의 좌표를 미리 받아두고, 각 cctv의 모든 경우의 수에 대해 완전탐색을 했습니다. 이 때, 감시된 구역이 겹칠 수 있으므로 visited를 int로 선언하고(지금 생각하니 배열 이름이 안맞네요) 0에서 1로 올라갈 때만 감시된 지역의 수를 증가시키고 반대로 다시 지울때는 1에서 0으로 내려갈 때만 감시된 지역의 수를 감소시켰습니다.

 

그 밖에는 특별한 것 없이 여타 재귀를 통한 완전탐색 문제와 비슷하게 풀 수 있었습니다.

 

추신) 확실히 오랜만에 코딩을 하니 잘 안풀리기도 하고 무엇보다 그냥 생각속에서 나오는대로 코딩했더니 제가 짠 코드를 설명으로 옮기는게 너무 어렵네요.. 제가 봐도 저게 뭔 말인지 중구난방해서 모르겠고.. 다시금 열심히 해야겠습니다.

 

#include<iostream>
#include<vector>
using namespace std;

int n, m, office[8][8], blindspot;
int visited[8][8];
vector<vector<vector<pair<int,int> > > > cctvDic; // n번째 - cctv방향 - 감시가능방향 - xy방향(pair)
vector<pair<int,int> > tmpdic = {make_pair(-1,0),make_pair(0,1),make_pair(1,0),make_pair(0,-1)};
vector<pair<int,int> > cctvLoc;

void cctvSetting(){
	for(int i=0; i<=5; i++){
		vector<vector<pair<int,int> > > tmp;
		cctvDic.push_back(tmp);
	}
	//1
	for(int i=0; i<4; i++){
		vector<pair<int,int> > tmp;
		tmp.push_back(tmpdic[i]);
		cctvDic[1].push_back(tmp);
	}
	//2
	for(int i=0; i<2; i++){
		vector<pair<int,int> > tmp;
		tmp.push_back(tmpdic[i]);
		tmp.push_back(tmpdic[i+2]);
		cctvDic[2].push_back(tmp);
	}
	//3
	for(int i=0; i<4; i++){
		vector<pair<int,int> > tmp;
		tmp.push_back(tmpdic[i]);
		tmp.push_back(tmpdic[(i+1)%4]);
		cctvDic[3].push_back(tmp);
	}
	//4
	for(int i=0; i<4; i++){
		vector<pair<int,int> > tmp;
		for(int j=0; j<4; j++){
			if(i==j) continue;
			tmp.push_back(tmpdic[j]);
		}
		cctvDic[4].push_back(tmp);
	}
	//5
	vector<pair<int,int> > tmp;
	tmp = tmpdic;
	cctvDic[5].push_back(tmp);
}

int paintWatch(int x, int y, pair<int,int> dic, bool paint){
	int increas = paint ? 1 : -1;
	int painter = 0;
	while(x>=0 && y>=0 && x<n && y<m && office[x][y]!=6){
		if(paint && visited[x][y]==0) painter++;
		if(!paint && visited[x][y]==1) painter++;
		visited[x][y]+=increas;
		x+=dic.first;
		y+=dic.second;
	}
	return painter;
}

int solve(int cctvcnt, int currentblind){
	if(cctvcnt == cctvLoc.size()){
		return currentblind;
	}
	int x = cctvLoc[cctvcnt].first;
	int y = cctvLoc[cctvcnt].second;
	int cctvKinds = office[x][y];
	int ans = 0;
	for(vector<pair<int,int> > cctv : cctvDic[cctvKinds]){ // cctv 방향 순환
		for(pair<int,int> ndic : cctv){
			currentblind += paintWatch(x,y,ndic,true);
		}
		ans = max(ans,solve(cctvcnt+1,currentblind));
		for(pair<int,int> ndic : cctv){
			currentblind -= paintWatch(x,y,ndic,false);
		}
	}
	return ans;
	
}

int main(){
	cctvSetting();
	cin>>n>>m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin>>office[i][j];
			if(office[i][j]==0) blindspot++;
			else if(office[i][j]<6) {cctvLoc.push_back(make_pair(i,j)); blindspot++;}
			else visited[i][j]=-1;
		}
	}
	cout<<blindspot-solve(0,0)<<endl;
}