백준 17142번: 연구소 3

[문제 링크]

17142번: 연구소 3

---

백트래킹과 BFS를 활용하여 풀 수 있는 문제였다.

 

입력으로 주어지는 바이러스들과 그 바이러스를 M개 활성화 시키는 모든 경우의 수를 백트레킹을 통해 완전탐색 하고, 모든 경우에 대해 바이러스를 확산시키는 BFS를 수행하여 가장 빠르게 확산되는 시간을 구해주면 원하는 결과를 얻을 수 있다.

 

시간이 0.25초로 제한되어 있기 때문에 2차원배열 전체를 순회하며 활성화 된 바이러스가 있는 위치를 찾아 확산시키는 방식으로 BFS를 구현하게 된다면 최악의 경우  (50^2) * (10개중 5개를 뽑는 조합의 수 252) * 50 =  31,500,000번 연산을 수행해야 하므로 제한 시간을 초과하게 된다. 따라서 배열 전체를 순회하는 방식이 아닌, 활성화 된 바이러스의 위치를 따로 저장하여 바이러스가 존재하는 좌표에 바로 접근할 수 있도록 구현하였다.

---

#include <iostream>
#include <cstring>
#include <queue>
#include <list>
using namespace std;

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N, M, cnt = 0, blank = 0;
int leastTime = INF;
int board[50][50];
Pos virus[10];

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

int bfs(list<Pos> actVirus) {
	bool visited[50][50] = { false };
	for (auto x : actVirus)
		visited[x.y][x.x] = true;

	int change = 0;

	queue <int> q;
	q.push(0);

	while (!q.empty()) {
		int time = q.front();
		q.pop();

		if (change == blank) return time;
//		bool isChange = false;

		int listSize = actVirus.size();
		for (int i = 0; i < listSize; i++) {
			Pos here = actVirus.front();
			actVirus.pop_front();

			for (int j = 0; j < 4; j++) {
				int nearY = here.y + dy[j];
				int nearX = here.x + dx[j];
				if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < N && !visited[nearY][nearX])
					if (board[nearY][nearX] == 2 || board[nearY][nearX] == 0) {
						visited[nearY][nearX] = true;
//						isChange = true;
						actVirus.push_back({ nearY, nearX });
						if (board[nearY][nearX] == 0)
							change++;
					}
			}
		}
//		if (isChange) q.push(time + 1);
		if (!actVirus.empty()) q.push(time + 1);
	}

	return INF;
}

void backtracking(int start, list<Pos>& actVirus) {
	int select = actVirus.size();
	if (select == M) {
		leastTime = min(leastTime, bfs(actVirus));
		return;
	}

	for (int i = start; i < cnt; i++) {
		Pos pos = virus[i];
		actVirus.push_back({ pos.y, pos.x });
		backtracking(i + 1, actVirus);
		actVirus.pop_back();
	}
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				virus[cnt].y = i;
				virus[cnt].x = j;
				cnt++;
			}
			else if (board[i][j] == 0)
				blank++;
		}

	list<Pos> actVirus;
	backtracking(0, actVirus);

	if (leastTime == INF)
		cout << -1 << endl;
	else
		cout << leastTime << endl;

	return 0;
}