백준 17142번: 연구소 3 (C++)

문제 링크 : www.acmicpc.net/problem/17142

 

 

<전체적인 알고리즘>

1. 바이러스가 있는 지점들을 모두 vector에 넣어주고 dfs로 m개의 모든 조합을 선택한다.

2. m개의 바이러스를 선택했으면 spread_bfs로 바이러스를 퍼뜨려준다.

3. 바이러스를 퍼뜨리며 시간을 위치에 기록한다.

4. 이차원 배열에 0이 존재하면 스킵, 다 퍼졌으면 최대시간을 반환한다.

5. 2,3,4를 반복하며 최소시간을 구한다.

 

 

<주의 사항>

바이러스가 퍼진 시간을 구할 때,,바이러스가 빈 공간에만 모두 퍼진시간을 구하는 것이다. 

즉 아직 비활성 상태의 바이러스에 더욱 퍼질 수 있어도 이미 빈공간에 다 퍼졌으면 그것이 최소시간이다.

 

<전체 코드>

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

using namespace std;

int n;
int map[52][52];
vector<pair<int, int>> start_virus;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool check[52][52];
int answer = 987654321;

class ins
{
public:
	int x, y, count;
	ins(int x, int y, int count)
	{
		this->x = x;
		this->y = y;
		this->count = count;
	}
};

int spread_bfs()        //바이러스 퍼뜨려보기
{
	fill(&check[0][0], &check[49][50], 0);
	int tmp[52][52];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			tmp[i][j] = map[i][j];  //퍼뜨려볼 임시 맵 복사
		}
	}

	queue<ins> q;
	for (int i = 0; i < start_virus.size(); i++)
	{
		int x = start_virus[i].first;
		int y = start_virus[i].second;
		q.push(ins(x,y,1));
		tmp[x][y] = 1;
		check[x][y] = true;
	}

	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int count = q.front().count;
		q.pop();

		for (int d = 0; d < 4; d++)
		{
			int nextx = x + dir[d][0];
			int nexty = y + dir[d][1];
			if (nextx < 0 || nexty < 0 || nextx >= n || nexty >= n)continue;
			if (tmp[nextx][nexty] == 1)continue;
			if (check[nextx][nexty])continue;
			check[nextx][nexty] = true;
			
		    if (tmp[nextx][nexty] == 0)  //빈 방이면 시간 넣어주기
			{
				tmp[nextx][nexty] = count + 1;
			}
			q.push(ins(nextx, nexty, count + 1));
		}
	}
	int maxx = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (tmp[i][j] == 0)return -1;  //빈 공간있으면 -1반환
			maxx = max(tmp[i][j], maxx);  //최대 시간
		}
	}
	return maxx-1; // 다 퍼진 시간 반환
}

void dfs(int count,int start,vector<pair<int,int>> &virus)  //바이러스 놓을 수 있는 곳 m개 조합으로 놓기
{
	if (count == 0)  //시작 바이러스 m개 선택 했으면,,
	{
		int result=spread_bfs();  //퍼뜨려보기
		if (result != -1) answer = min(answer, result);
		return;
	}
	for (int i = start; i < virus.size(); i++)
	{
		start_virus.push_back(virus[i]);
		dfs(count - 1, i + 1, virus);
		start_virus.pop_back();
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int m;
	cin >> n >> m;
	vector<pair<int,int>> virus;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 2)
			{
				virus.push_back(make_pair(i, j));  //바이러스 놓을 수 있는 곳 저장
				map[i][j] = -1;
			}
		}
	}
	
	dfs(m, 0, virus);
	if (answer == 987654321)answer = -1;
	cout << answer;
	
	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.