백준 17142번 연구소 3 (c++)

 

이런 탐색에 시뮬레이션까지 해야하는 문제는 문제를 잘 읽어야 하며, 때로는 문제를 읽어도 잘 알 수 없는 묘한 조건에 걸려 시간을 왕창 낭비하는 일이 빈번하다.

이 문제는 상당히 까다로운 조건에 시간제한까지 빡빡하여 고생했다

 

int n, m;
vector<pair<int, int>> virus;
vector<vector<int>> mp;

int active[10] = { 0, };

int mx[4] = { 1,0,-1,0 };
int my[4] = { 0,-1,0,1 };

int ans = 210000000;

바이러스의 위치와 갯수를 알아놓아야 하기 때문에 virus 배열을 선언하고

DFS를 돌며 마킹할 active 배열을 선언한다

하나의 상태가 완성되면 전염에 걸리는 시간을 구해 ans와 비교해 저장한다.

 

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	bool flag = false;
	for (int i = 0; i < n; i++)
	{
		vector<int> tmp;
		for (int j = 0; j < n; j++)
		{
			int a;
			cin >> a;
			if (a == 0) // 공백
			{
				flag = true;
				tmp.push_back(0);
			}
			else if (a == 1) // 벽
			{
				tmp.push_back(-1);
			}
			else if (a == 2) // 바이러스
			{
				virus.push_back({ j,i });
				tmp.push_back(0);
			}
		}
		mp.push_back(tmp);
	}
	if (flag == false)
	{
		cout << 0 << endl;
		return 0;
	}
	sol(0, 0);
	if (ans == 210000000)
	{
		cout << -1 << endl;
	}
	else cout << ans - 1 << endl;
}

 

맵을 구성한다

0인경우 빈칸이므로 그대로 기록

1인경우 벽이므로 -1을 기록한다.(맵에 시간을 기록할 것이므로 양수이면 곤란)

2는 바이러스이므로 해당 좌표를 virus 배열에 저장, 바이러스칸도 어쨋든 전염될 수 있는 공간이므로 편의상 0으로 비워준다.

 

flag 는 한칸이라도 빈칸이 있는지 검사하는데, 바이러스는 문제의 조건에서 1개 이상이라고 보장해 주었지만

빈공간이 애초부터 한칸도 없으면 탐색할 필요도 없고 전염에 걸리는 시간도 0도가 되므로 바로 프로그램을 종료해줘야 한다.

void sol(int idx, int cnt)
{
	if (cnt == m)
	{
		simulation();
		return;
	}
	for (int i = idx; i < virus.size(); i++)
	{
		if (active[i] == 1) continue;
		active[i] = 1;
		sol(i + 1, cnt + 1);
		active[i] = 0;
	}
}

 

dfs 돌리는 함수이다.

활성화 할 수 있는 바이러스는 최대 m개이므로 재귀 깊이는 m번으로 충분하다.

dfs로 모든 경우의수를 만들어 해당 상태일때 전염을 시뮬레이션 한다.

 

void simulation()
{
	vector<vector<int>> wall;
	queue<pair<int, int>> q;
	int countZero = 0;
	wall = mp;
	int qsize = 0;
	
	for (int i = 0; i < virus.size(); i++)
	{
		if (active[i] == 1)
		{
			q.push({ virus[i].first,virus[i].second });
			wall[virus[i].second][virus[i].first] = 1;
		}
		else
		{
			wall[virus[i].second][virus[i].first] = -2;
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (wall[i][j] == 0)countZero++;
		}
	}
	qsize = q.size();
	while (qsize-->0)
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + mx[i];
			int ny = y + my[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (wall[ny][nx] == 0 || wall[ny][nx] == -2)
			{
				if (wall[ny][nx] == 0)countZero--;
				wall[ny][nx] = wall[y][x] + 1;
				q.push({ nx,ny });
			}
		}
		if (qsize == 0)
		{
			if (countZero == 0)
			{
				ans = min(ans, status(wall));
				return;
			}
			qsize = q.size();
		}
	}
}

문제의 핵심

 

시뮬레이션할때 주의할점은 비활성 바이러스의 존재이다.

비활성 바이러스도 감염이 가능한 칸이다.

하지만 비활성인 상태로도 감염인 상태가 인정된다.

즉 시뮬레이션을 돌릴때 모든칸이 감염인 상태를 종료 조건으로 설정하면 비활성 바이러스인 칸도 열심히 감염시키려고 시간을 소모하므로 오답이다.

예를들어

 

4 1

1 1 1 1

2 0 2 1

1 1 1 1

1 1 1 1

 

인 경우

둘중 하나의 바이러스를 활성화 하고 중앙에 빈칸을 감염시킨 시점에서 모든칸에 바이러스가 존재하므로 종료되어야 한다.

그래서 한 턴이라는 개념이 중요하며, 나는 qsize를 통해 한턴에 돌아야 할 루프 횟수를 기억하게 해 주었다.

다음 턴이 없으면 당연히 종료

 

그리고 한 턴이 지날때마다 모든 칸이 바이러스로 꽉 차있는지 확인해야하는데

그때마다 모든칸을 확인했더니 시간초과를 받았다.

 

그래서 시작하기 전에 미리 빈칸의 수를 저장해두고, 빈칸을 바이러스로 감염시킬때마다 저장된 수를 감소시켜

매번 전체 탐색을 하지 않아도 빈칸이 꽉 찼는지 판단 할 수 있게 해주었다.

 

빈칸이 꽉 찼으면

int status(vector<vector<int>>& wall)
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//cout << wall[i][j] << " ";
			if (wall[i][j] != -1)
			{
				if (wall[i][j] == 0) return -1;
				else cnt = max(cnt, wall[i][j]);
			}
		}
		//cout << "\n";
	}
	//cout << "\n";
	return cnt;
}

모든 칸을 체크하여 가장 나중에 감염된 칸을 체크하여 그 숫자를 반환한다.

 

참고로 나는 바이러스의 배치를 1로 표시했고, 시간의 경과를 칸+1로 표시했기 때문에

최종 결과는 ans에서 1을 빼줘야 한다.