백준 17142번 _ 연구소 3

2020-04-14 · 배운 것 · 7분 읽기

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

자료형 선언

vector<pair<int, int>>virusPoint;
int map[52][52];
bool visit[52][52];
int targetPlace;
int virusPlace;
int N, M;

풀이방법 및 주의사항

이 문제는 1)virus가 선택될수 있는 모든 조합을 찾아 2)시뮬레이션을 돌려보고 3)그 중에서 최소시간을 출력하는 문제이다.

1) next_permutation 함수를 이용해서 모든 조합을 간단히 구현하였다.
2) 밑의 그림을 보면 구조를 알수있다.

3) 생략

함수설명

//빈공간이 없이 virus가 확산되었는지 확인하는 함수
bool isFull()
//visit 배열 초기화
void visitInit()
//targetPlace 초기화 및 map, virusPoint입력 
void Input()
//한 좌표에 대해 확산, 다음좌표 저장
void diffusionVirus(int y, int x, vector<pair<int, int>>& next)
//조합으로 선택된 바이러스를 이용하여 시뮬레이션을 돌리는 함수, 완료시간을 return 
int simulation(const vector<pair<int, int>>& selectVirus)
//virusPoint중 M개를 선택하는 경우를 조합하여 시뮬레이션을 돌리는 함수,
//그중 최소시간을 출력
void solve()

전체코드

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

using namespace std;

vector<pair<int, int>>virusPoint;
int map[52][52];
bool visit[52][52];
int targetPlace;
int virusPlace;
int N, M;

bool isFull()
{
	if (virusPlace == targetPlace)
		return true;
	return false;
}

void visitInit()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			visit[i][j] = false;
}

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

//한동작
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
void diffusionVirus(int y, int x, vector<pair<int, int>>& next)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (visit[ny][nx])
			continue;
		if (!(ny >= 0 && nx >= 0 && ny < N && nx < N))
			continue;
		if (map[ny][nx] == 1)
			continue;
		if (map[ny][nx] != 2)
			virusPlace++;

		visit[ny][nx] = true;
		next.push_back({ ny, nx });
	}
}

int simulation(const vector<pair<int, int>>& selectVirus)
{
	vector<pair<int, int>> presentVirus = selectVirus;
	vector<pair<int, int>> nextVirus;
	int cnt = 0;
	while (1)
	{
		for (auto& virus : presentVirus)
		{
			int y = virus.first;
			int x = virus.second;
			visit[y][x] = true;

			//fill empty place
			diffusionVirus(y, x, nextVirus);
		}
		presentVirus = move(nextVirus);
		cnt++;
		if (isFull())
			break;
		if (presentVirus.size() == 0)
			return INT_MAX;
	}
	return cnt;
}

void solve()
{
	int answer = INT_MAX;
	vector<int> virus;
	virus.resize(virusPoint.size());

	for (int i = 0; i < M; i++)
		virus[i] = 1;

	sort(begin(virus), end(virus));

	//조합
	do
	{
		vector<pair<int, int>> selectVirus;
		for (int i = 0; i < (int)virus.size(); i++)
			if (virus[i] == 1)
				selectVirus.push_back(virusPoint[i]);

		//이제 고른 바이러스들로 풀어보기
		answer = min(answer, simulation(selectVirus));
		visitInit();
		virusPlace = virusPoint.size();
	} while (next_permutation(begin(virus), end(virus)));

	if (answer == INT_MAX)
		cout << -1 << endl;
	else
		cout << answer << endl;
}

int main()
{
	Input();
	if (isFull())
	{
		cout << 0 << endl;
		return 0;
	}

	solve();
	return 0;
}

후기

비활성화 바이러스를 만났을때 처리방법이라던가, 바이러스가 전부확산된것을 어떻게 알것인가, 조합을 어떤식으로 구현할것인가 등등등 생각할거리가 많은 문제였다.
이런 문제는 일단 글로 전체 코드의 구조를 만들어보고 짜봐야 실수가 덜할것 같다.