백준 17142 연구소3 [BFS]

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

17142번: 연구소 3

문제 풀이

문제 설명이 생각보다 길어서 중간에 집중력이 흐려질 수 있습니다.

 

문제를 읽고 헷갈리는 점은 다음과 같습니다.

"활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성화된다."

애매모호하지만 생각해보면 간단하게 아래와 같이 정리가 됩니다.

 

2****이면, 1초 후에는 2(활성 바이러스)가  옆 칸에 도달하면서 22***이 됩니다.

이를 시간에 따른 맵을 아래와 같이 시뮬레이션이 됩니다.

 

0초 2****

1초 22***

2초 222**

3초 2222*

4초 22222

 

문제를 쪼개서 순서를 세우면 다음과 같습니다.

1. 입력을 받습니다. (이때 바이러스 위치와 안전 구역을 카운트 및 저장해줍니다.)

2. 총 바이러스의 수에서 M개를 뽑습니다. 선택되지 않은 바이러스들은 비활성 바이러스가 됩니다.

3. M개를 뽑았다면, 각 좌표에서 bfs 알고리즘을 적용해서 시간 별로 전파시킵니다.

 

저는 방문 배열을 따로 만들어서 중복되는 곳에는 다시 가지 않도록 체크했습니다.

 

예시)

4 2 

0 1 1 0

2 1 1 2

2 1 1 2

0 1 1 0

 

만약에 (1, 0), (1, 3)을 활성 바이러스로 두고 보면 (저는 활성 바이러스는 5로 설정했습니다)

safe_zone = 4

 

0 1 1 0

5 1 1 5

2 1 1 2

0 1 1 0

 

1초 후, 감염된 구역을 4로 표시했습니다.

중요한 점은 비활성 바이러스도 활성 바이러스가 지나가면, 이 역시 감염됩니다.

safe_zone = 2

 

4 1 1 4

5 1 1 5

4 1 1 4

0 1 1 0

 

2초 후,

safe_zone = 0

 

4 1 1 4

5 1 1 5

4 1 1 4

4 1 1 4

 

2초가 지났을 때, safe_zone이 0이므로 모든 구역이 감염이 되었기 때문에 답을 갱신해줍니다.

 

소스 코드

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

#define MAX 51
using namespace std;

int N, M, safe_zone, copy_zone, ans = 987654321;
int stage[MAX][MAX];
int copy_stage[MAX][MAX];
bool visit[MAX][MAX];

int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

vector<pair<int, int>> all_virus;
bool choice_virus[10];

// 바이러스 퍼트리기
void BFS(vector<pair<int, int>>& v)
{
	int time = 0;

	// 애초에 안전 구역이 0인 경우는 전파하지 않아도 된다.
	if (copy_zone == 0)
	{
		ans = 0;
		return;
	}

	queue<pair<int, int>> q;
	for (int i = 0; i < v.size(); i++) q.push({ v[i].first, v[i].second });

	while (!q.empty())
	{
		time++; // 1초 증가

		int cycle = q.size();
		for (int i = 0; i < cycle; i++)
		{
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int j = 0; j < 4; j++)
			{
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx >= 0 && ny >= 0 && nx < N && ny < N)
				{
					
					if (visit[nx][ny] == true) continue;

					if (copy_stage[nx][ny] == 0 || copy_stage[nx][ny] == 2)
					{
						//cout << "[" << nx << "," << ny << "]" << endl;
						if (copy_stage[nx][ny] == 0) copy_zone--;

						visit[nx][ny] = true;
						copy_stage[nx][ny] = 4;
						q.push({ nx,ny });
					}
				}
			}
		}

		// 바이러스를 전파시켰는데, 안전 구역이 하나도 없다면
		if (copy_zone == 0)
		{
			ans = min(ans, time);
			return;
		}
	}
}

void CopyMap()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			copy_stage[i][j] = stage[i][j];
		}
	}
}

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


// 바이러스 M개 뽑기
void Select_Virus(int index, int cnt)
{
	if (cnt == M)
	{
		CopyMap();    // 맵 복사
		Initialize(); // 방문배열 초기화 
		copy_zone = safe_zone; // 안전한 구역 초기화
		vector<pair<int, int>> virus; // 활성 바이러스 위치
		for (int i = 0; i < 10; i++)
		{
			if (choice_virus[i] == true)
			{
				virus.push_back({ all_virus[i].first , all_virus[i].second });
				copy_stage[all_virus[i].first][all_virus[i].second] = 5;
				visit[all_virus[i].first][all_virus[i].second] = true;
			}
		}

		// 바이러스 전파
		BFS(virus);
	}

	for (int i = index; i < all_virus.size(); i++)
	{
		if (choice_virus[i] == true) continue;
		choice_virus[i] = true;
		Select_Virus(i, cnt + 1);
		choice_virus[i] = false;
	}
}


int main()
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> stage[i][j];
			if (stage[i][j] == 2) all_virus.push_back({ i,j });
			else if (stage[i][j] == 0) safe_zone++;
		}
	}

	Select_Virus(0, 0);
	if (ans == 987654321) cout << -1;
	else cout << ans;
	return 0;
}