BOJ : 14502 연구소

 

---

[BOJ 14502(G5) 리뷰]

연구소에 벽을 3개 설치할 수 있다. 벽을 설치한 후에 연구실에 있는 바이러스는 빈 공간으로 퍼져 나간다. 벽으로 막혀있다면 더 이상 퍼져나가지 않는다.

연구소에 벽을 3개 설치하는 경우 중에서 가장 적게 바이러스가 퍼질때 바이러스가 퍼지지않는 칸의 개수를 구하는 문제이다.

백트래킹+BFS로 문제를 해결했다. 먼저 벽을 3개 세우는 경우를 백트래킹을 통해 하나씩 확인해주고, 각각의 경우에 대해 BFS를 수행하여 바이러스가 퍼지게 한 다음 바이러스가 퍼지지 않는 공간의 갯수를 세면 된다.

시간초과를 걱정하며 문제를 풀었는데 채점TC가 느슨해서인지 정답은 나왔지만 예제에 나온 테스트케이스는 제시간에 답이 안나왔다. 조합을 사용하여 최대한 속도를 줄였지만 그래도 맵은 크고 초기에 주어진 벽이 적은경우에는 시간이 오래걸린다. 어떻게 해결해야 할지 고민해봐야 겠다.

---

#include <iostream>
#include <queue>
#include <deque>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
#define X first
#define Y second

int map[8][8];
int N, M;
bool isUsed[9][9];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int ans = 0;
vector <pair<int, int>> virus;




void bfs()
{
	int temp[8][8];
	memcpy(temp, map, sizeof(temp));
	for (int i = 0; i < N; i++)
		fill(isUsed[i], isUsed[i] + M, 0);

	int len = virus.size();
	for (int k = 0; k < len; k++)
	{
		auto start = virus[k];
		int i = start.first;
		int j = start.second;
		if (isUsed[i][j]) continue;

		queue < pair<int, int>> Q;
		Q.push({ i,j });
		isUsed[i][j] = 1;
		while (!Q.empty())
		{
			auto cur = Q.front(); Q.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
				if (temp[nx][ny] != 0 || isUsed[nx][ny]) continue;
				temp[nx][ny] = 2;
				Q.push({ nx,ny });
				isUsed[nx][ny] = 1;
			}
		}
	}


	int cnt = 0;
	//cout << '\n';
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//cout << temp[i][j] << ' ';
			if (temp[i][j] == 0) cnt++;
		}
		//cout << '\n';
	}
	//cout << '\n';
	ans = max(ans, cnt);
}

void Run(int n, int x, int y)
{
	if (n == 3)
	{
		//cout << '\n';
		//for (int i = 0; i < N; i++)
		//{
		//	for (int j = 0; j < M; j++)
		//	{
		//		cout << map[i][j] << ' ';
		//	}
		//	cout << '\n';
		//}
		//cout << '\n';
		bfs();
		return;
	}

	for (int i = x; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] != 0) continue;
			map[i][j] = 1;
			Run(n + 1, i, j);
			map[i][j] = 0;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 2) virus.push_back({ i,j });
		}
	}
	Run(0, 0, 0);
	cout << ans;
}