백준 14502번 _ 연구소

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

14502번: 연구소

풀이방법

1. 벽을 세울 조합을 구해서 -> next_permutaion이용

2. 바이러스 퍼지는것 시뮬레이션 -> dfs

---

시간복잡도

조합 -> 최대 60C3 

바이러스 퍼지는것 시뮬레이션 -> 최대 8*8

 

주어진 시간은 2초 (약 2억개의 연산)이므로 시간은 어떻게 풀어도 충분함. 

---

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int>> emptyPlace;
vector<vector<int>>map;
vector<pair<int, int>> virusPos;
int N, M;

void Input()
{
	cin >> N >> M;
	map.resize(N+2);
	for (int i = 0; i < N; i++)
		map[i].resize(M+2);
	int value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> value;
			map[i][j] = value;
			if (value == 0)
				emptyPlace.push_back({ i, j });
			else if (value == 2)
				virusPos.push_back({ i,j });
		}
	}
}

int countEmptyPlace(const vector<vector<int>>& cmap)
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (cmap[i][j] == 0)
				cnt++;
	return cnt;
}

bool inRange(int y, int x)
{
	if (y >= 0 && x >= 0 && y < N && x < M)
		return true;
	return false;
}

int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
void dfs(int y, int x, vector<vector<int>>& cmap)
{
	//감염
	cmap[y][x] = 2;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (inRange(ny, nx) == false)
			continue;
		if (cmap[ny][nx] == 0)
			dfs(ny, nx, cmap);
	}
}

int simulation(const vector<int>& choose)
{
	//벽 세우기
	vector<vector<int>> calMap = map;
	for (auto& ele : choose)
	{
		int y =emptyPlace[ele].first;
		int x = emptyPlace[ele].second;
		calMap[y][x] = 1;
	}

	int ans = 0;
	for (auto& virus : virusPos)
	{
		//dfs ㄱㄱㄱ
		dfs(virus.first, virus.second, calMap);
	}
	ans = countEmptyPlace(calMap);

	return ans;
}

void solve()
{
	int maxValue = 0;
	vector<int>option;
	option.resize(emptyPlace.size());
	for (int i = 0; i < 3; i++)
		option[i] = 1;
	sort(begin(option), end(option));

	do
	{
		vector<int>choose;
		for (int i = 0; i < (int)option.size(); i++)
		{
			if (option[i] == 1)
				choose.push_back(i);
		}

		//simulation ㄱㄱ
		maxValue = max(maxValue, simulation(choose));
	} while (next_permutation(begin(option), end(option)));
	
	cout << maxValue;
}

int main()
{
	Input();
	solve();
	return 0;
}

---

후기

구현량은 꽤나 있지만, 정답비율 50퍼센트가 넘는 쉬운문제였다.