[BOJ] 17142 : 연구소 3 (코드개선) - travelbeeee

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

기존풀이 :  https://travelbeeee.tistory.com/332

---

[ 알고리즘풀이 ]

■ 연구소의 사이즈는 N, 바이러스의 개수는 M ( map을 입력받으면서 '0' 인 공간을 미리 count 해둔다. )

■ 바이러스를 M개 뽑아서 감염을 확산시킬 것이므로, 바이러스의 위치를 vir 에 저장한다.

■ Backtracking 을 이용해 vir에 저장된 바이러스 중 M개를 뽑는다.

■ 뽑힌 M개의 바이러스를 BFS 탐색을 이용해 감염을 확산시킨다. ( '0' 인 공간을 탐색하면 count )

 이때, 탐색을 하면서 Time 을 count 해주고, 앞으로 밟아야 하는 땅이 '0' 이라면, realTime을 Time 값으로 갱신해준다.

 기존의 코드는 현재 밟은 땅들이 모두 '2' 이고, 앞으로 탐색할 곳이 없을 때를 찾기 위해 bool check1, check2를 이용했다. 이 부분을 조금 더 간결하게 코딩하기 위해 실제로 내가 탐색하는데 필요한 realTime 과 그냥 탐색이 진행될 때마다 시간을 count 해주는 Time 변수 두 개를 이용했다. 코드가 실제로 눈에 띄게 짧아진 것은 아니지만 가독성 면에서 조금 더 간결한 코드이지않을까 싶다...!

■ BFS 탐색을 하며 count 한 값과 (1) 에서 count 한 값을 비교해 모든 지역에 감염이 진행되었다면, realTime과 답을 비교해 답을 갱신한다.

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 987654321

using namespace std;

vector<pair<int, int>> vir;
int N, M, spaceCount, ans = INF, map[50][50], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool choice[10];

void spreadVirus(void) {
	bool visited[50][50] = {};
	queue<pair<int, int>> q;
	for (int i = 0; i < vir.size(); i++)
		if (choice[i]) {
			q.push({ vir[i].first, vir[i].second });
			visited[vir[i].first][vir[i].second] = 1;
		}

	int realTime = 0, time = 0, cnt = 0;
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nextX = cur.first + dx[j], nextY = cur.second + dy[j];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
					if (map[nextX][nextY] != 1 && !visited[nextX][nextY]) {
						visited[nextX][nextY] = 1;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0) {
							cnt++;
							realTime = time + 1;
						}
					}
				}
			}
		}
		time++;
	}

	if (cnt == spaceCount)
		ans = min(ans, realTime);

	return;
}

void Backtracking(int s, int cnt) {
	if (cnt == M) {
		spreadVirus();
		return;
	}
	for (int i = s; i < vir.size(); i++) {
		choice[i] = true;
		Backtracking(i + 1, cnt + 1);
		choice[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				spaceCount++;
			if (map[i][j] == 2)
				vir.push_back({ i, j });
		}
	}

	Backtracking(0, 0);

	(ans == INF) ? cout << -1 : cout << ans;
}

---