[백준/BOJ] 백준 17141번 : 연구소 2

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

17141번: 연구소 2

바이러스를 놓을 자리 m개를 고르고 바이러스를 퍼뜨려서 모든 빈칸에 바이러스가 퍼지는 가장 빠른 시간을 구한다

 

코드

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

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

//바이러스가 모든 빈칸에 퍼졌는지 확인
bool Check()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == 0)
				return false;
		}

	return true;
}

void boardCopy(int to[][50], int from[][50])
{
	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
			to[i][j] = from[i][j];
}

//바이러스를 퍼뜨린다
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();

		board[here.first][here.second] = 3; //바이러스가 퍼지는 곳은 3으로 체크한다

		//바이러스가 모두 퍼졌는지 확인
		if (Check())
		{
			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] == 0 && 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)
	{
		boardCopy(board, temp_board);
		return virusSpread(selected);
	}

	int ret = 987654321;

	for (int i = 0; i < can_virus_seat.size(); i++)
	{
		//중복선택을 피하기 위한 조건
		if (last_selected_number < i)
		{
			selected.push_back(can_virus_seat[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 == 2)
			{
				can_virus_seat.push_back(make_pair(i, j));
				board[i][j] = 0; //board에는 빈칸과 같은 0을 넣는다
			}

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

	//원본 board를 저장해 놓는다
	boardCopy(temp_board, board);

	result = Solve(selected, -1);

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

	return 0;
}