연구소 2 (feat. 백준, 17141번)

연구소 2
https://www.acmicpc.net/problem/17141

17141번: 연구소 2

반응형

// woohyeon.kim
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M;
int map[51][51];
int tmp[51][51];
bool visit[51][51];
vector<pair<int, int>> virus_list, all_virus_list;
vector<int> result_times;

int virus(vector<pair<int, int>>& virus_list)
{
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			// 벽이면
			if (map[ix][iy] == 1)
				tmp[ix][iy] = -2;
			else
				tmp[ix][iy] = -1;
			visit[ix][iy] = false;
		}
	}
	queue<pair<int, int>> q;
	for (const auto& virus : virus_list)
	{
		q.push(virus);
		visit[virus.first][virus.second] = true;
		tmp[virus.first][virus.second] = 0;
	}
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };

	while (!q.empty())
	{
		pair<int, int> pos = q.front(); q.pop();
		auto x = pos.first; auto y = pos.second;
		for (auto idx = 0; idx < 4; ++idx)
		{
			auto nx = x + dx[idx]; auto ny = y + dy[idx];
			if (0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny] && tmp[nx][ny] != -2)
			{
				visit[nx][ny] = true;
				q.push(make_pair(nx, ny));
				tmp[nx][ny] = tmp[x][y] + 1;
			}
		}
	}

	auto time = 0;
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			if (tmp[ix][iy] == -1)
				return -1;
			time = max(time, tmp[ix][iy]);
		}
	}
	return time;
}

void dfs(int index, int count)
{
	if (count == M)
	{
		result_times.push_back(virus(virus_list));
	}
	else
	{
		for (auto idx = index; idx < static_cast<int>(all_virus_list.size()); ++idx)
		{
			virus_list.push_back(all_virus_list[idx]);
			dfs(idx + 1, count + 1);
			virus_list.pop_back();
		}
	}
}

int main()
{
	cin >> N >> M;
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			cin >> map[ix][iy];
			if (map[ix][iy] == 2)
				all_virus_list.push_back(make_pair(ix, iy));
		}
	}

	dfs(0, 0);
	result_times.erase(remove(result_times.begin(), result_times.end(), -1), result_times.end());
	if (result_times.empty())
		cout << -1 << endl;
	else
		cout << *min_element(result_times.begin(), result_times.end()) << endl;

	return 0;
}
// *&)*@*

연구소 3을 풀고 풀었더니 10분만에 풀어버렸어요~~!!

1. 바이러스의 모든 위치를 구한다. (MM개라고 하면)
2. MM개중 M개에 대한 조합을 구한다.
3. 조합에 바이러스를 심고 전체 bfs로 확산했을때 최대 시간을 구한다. (단, -1이 있는 경우 -1 리턴)
4. 모든 조합으로 바이러스를 퍼뜨렸을때의 최소 시간을 구한다. (단, -1만 있을 경우 -1 리턴)