[백준/BOJ] 백준 17142번 : 연구소 3

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

17142번: 연구소 3

활성 바이러스가 될 수 있는 자리를 고르고, 바이러스가 확산되는 것을 확인한다. 모든 빈칸에 바이러스가 퍼졌는지 확인하는 방법은 처음 board를 입력받을 때 빈칸의 개수를 세서 저장해 놓고, 바이러스가 빈칸으로 퍼질 때 하나씩 마이너스하여 그  개수가 0이 되면 모든 빈칸에 바이러스가 퍼졌다고 판단하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
using namespace std;

int n, m;
int board[50][50];
int discovered[50][50];
int depth[50][50];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int zero_num = 0;
int temp_zero_num;
vector<pair<int, int>> can_move_virus;

//고른 활성바이러스가 퍼지는것을 표현
int virusSpread(vector<pair<int, int>>& selected)
{
	memset(discovered, 0, sizeof(discovered));
	memset(depth, 0, sizeof(depth));

	queue<pair<int, int>> q;

	for (int i = 0; i < selected.size(); i++)
	{
		discovered[selected[i].first][selected[i].second] = 1;
		depth[selected[i].first][selected[i].second] = 0;

		q.push(selected[i]);
	}

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		if (board[here.first][here.second] == 0)
			zero_num--;

		//모든 빈칸에 바이러스가 퍼졌을때
		if (zero_num == 0)
			return depth[here.first][here.second];

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] != 1 && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				q.push(there);
			}
		}
	}

	return 987654321;
}

int Solve(vector<pair<int, int>>& selected, int last_selected_number)
{
	//활성 바이러스가 될 바이러스 m개를 골랐을때
	if (selected.size() == m)
	{
		zero_num = temp_zero_num;
		return virusSpread(selected);
	}

	int ret = 987654321;

	for (int i = 0; i < can_move_virus.size(); i++)
	{
		//중복된 선택을 방지하기 위한 조건
		if (last_selected_number < i)
		{
			selected.push_back(can_move_virus[i]);
			ret = min(ret, Solve(selected, i));
			selected.pop_back();
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;
	vector<pair<int, int>> selected;
	int result;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input;

			//빈칸의 개수를 저장한다
			if (input == 0)
				zero_num++;

			if (input == 2)
			{
				//활성 바이러스가 될 수 있는 자리를 저장한다
				can_move_virus.push_back(make_pair(i, j));
				board[i][j] = 2;
			}

			else
				board[i][j] = input;
		}

	temp_zero_num = zero_num; //빈칸의 개수를 저장해 놓는다

	result = Solve(selected, -1);

	if (result == 987654321)
		cout << -1;
	else
		cout << result;

	return 0;
}