연구소 3 (feat. 백준, 17142번)

연구소 3
https://www.acmicpc.net/problem/17142

17142번: 연구소 3

반응형

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

using namespace std;

int N, M;
int maps[51][51];
int node[51][51];
bool visit[51][51];
vector<pair<int, int>> virus_lists;
vector<pair<int, int>> all_virus_lists;
int dx[4], dy[4];
vector<int> take_times;

int virus()
{
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			visit[ix][iy] = false;
			if (maps[ix][iy] == 1)
				node[ix][iy] = -3;
			else if (maps[ix][iy] == 2)
				node[ix][iy] = -1;
			else
				node[ix][iy] = -1;
		}
	}
	queue<pair<int, int>> q;
	for (const auto& item : virus_lists)
	{
		q.push(item);
		visit[item.first][item.second] = true;
		node[item.first][item.second] = 0;
	}

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

	auto take_time = 0;
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			if (maps[ix][iy] == 2)
				continue;
			if (node[ix][iy] == -1)
				return -1;
			take_time = max(take_time, node[ix][iy]);
		}
	}
	return take_time;
}

void dfs(int index)
{
	if (virus_lists.size() == M)
	{
		take_times.push_back(virus());
	}
	else
	{
		for (auto idx = index; idx < static_cast<int>(all_virus_lists.size()); ++idx)
		{
			virus_lists.push_back(all_virus_lists[idx]);
			dfs(idx + 1);
			virus_lists.pop_back();
		}
	}
}

int main()
{
	dx[0] = 1, dx[1] = -1, dx[2] = 0, dx[3] = 0;
	dy[0] = 0, dy[1] = 0, dy[2] = 1, dy[3] = -1;

	cin >> N >> M;
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			cin >> maps[ix][iy];
			if (maps[ix][iy] == 2)
				all_virus_lists.push_back(make_pair(ix, iy));
		}
	}
	dfs(0);

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

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

bfs나 permutation을 구하는 것 외에 문제상의 포인트가 있습니다.

1. 비활성화 바이러스를 만나도 현재 + 1 을 취해주고, 비활성화 바이러스의 좌표로 가서 상하좌우를 똑같이 해주면 됩니다.
2. 단, 여기서 포인트는 시간에는 포함되지 않습니다. 즉, 비활성화 바이러스의 시간이 10이고 이때 최대가 10이더라도 10은 제외해주어야 합니다.
3. 사방이 벽이고 바이러스만 있는 경우, 답은 항상 0이어야 합니다. 왜냐면 +1씩 시간은 흘러가지만 비활성화 바이러스는 시간에서 제외해야 하기 때문이고, 사방을 전염시킨 것이기 때문에 -1은 아닙니다.