백준 알고리즘 14502번 - 연구소

처음에는 이걸 어떻게 풀지? 라는 생각이 들었던 문제.

map의 크기가 작아서 브루트 포스로 걍 다 막아보면 된다.

재귀를 통해서 막을 수도 있을 것같지만, 나는 for문 3개를 돌려(...) 직접 다 막아보았다.

 

time error가 나는 거 아닐까? 라는 생각이 들었지만 맵의 최대크기가 64이므로, 그럴 일은 없을 것같다.

(모두 다 빈칸이라고 해도 64개중에 3개를 고르는 경우의 수는 64*63*62이므로 1억을 넘지않는다.)

 

그리고 바이러스를 퍼트리는 함수를 결정해야하는데 나는 dfs를 통해서 퍼트리는 것으로 구현하였다.

 

3개를 막고, 바이러스 퍼트리고, 숫자를 센 뒤, 초기화 하는 과정을 거쳤다.

처음 입력받을 때부터, 맵을 표현하는 배열을 두 개 만들었다. 하나는 계속해서 바꿔갈 맵을

또 다른 배열은 초기화를 위해 구현하였다.

 

문제 자체는 어렵지 않아서 소스 코드와 주석을 보면 이해가 쉬울 것같다.

 

//가능한 좌표를 벡터에 쳐넣으면됨
#include <iostream>
#include <vector>

using namespace std;

//(0,0)좌표를 넣을 벡터
vector<pair<int,int> > v;
int map[9][9];
int og[9][9];

int width,height;

//dfs사용시 움직이는 방향
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};

//3개를 막는 함수
void block(int firstX,int firstY,int secondX,int secondY,int thirdX,int thirdY)
{
	map[firstY][firstX]=1;
	map[secondY][secondX]=1;
	map[thirdY][thirdX]=1;
}
//안전지대 세는 함수
int count()
{
	int counts=0;
	for(int y=1;y<=height;y++){
		for(int x=1;x<=width;x++){
			if(map[y][x]==0) counts++;
		}
	}
	return counts;
}
//바이러스 퍼트리는 함수
void dfs(int x,int y)
{
	map[y][x]=2;
	int nowX,nowY;
	for(int i=1;i<=4;i++){
		nowX=x+dx[i];
		nowY=y+dy[i];
		if(nowX>=1 && nowX<=width && nowY>=1 && nowY<=height){
			if(map[nowY][nowX]==0) {
				dfs(nowX,nowY);
			}
		}
	}
}
//초기화

void init()
{
	for(int y=1;y<=height;y++){
		for(int x=1;x<=width;x++){
			map[y][x]=og[y][x];
		}
	}	
}

int main()
{
	cin>>height>>width;
	
	for(int y=1;y<=height;y++){
		for(int x=1;x<=width;x++){
			scanf("%d",&map[y][x]);
			og[y][x]=map[y][x];
			if(map[y][x]==0)
				v.push_back(make_pair(x,y));
		}
	}
	
	int max=0,num;
	int vSize=v.size();
	for(int i=0;i<vSize-2;i++){
		for(int j=i+1;j<vSize-1;j++){
			for(int k=j+1;k<vSize;k++){
				//3개 골라서 막음
				block(v[i].first,v[i].second,v[j].first,v[j].second,v[k].first,v[k].second);
				//바이러스 퍼트림
				
				for(int y=1;y<=height;y++){
					for(int x=1;x<=width;x++){
						if(map[y][x]==2) dfs(x,y);
					}
				}
				//안퍼트려진 곳 찾아서 num에 저장
				num=count();
				if(num>max) max=num;
				init();
			}
		}
	}
	cout<<max;
}