BOJ 17142 - 연구소 3

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

문제

연구소에 이미 존재하는 바이러스들 중 $m~(2\le m \le 10)$개를 활성 상태로 바꾸어 바이러스를 퍼뜨리는 문제이다. 그 때, 연구소의 모든 빈칸에 바이러스가 퍼지게 하는 최소 시간을 구해야 한다.

풀이

연구소에 존재하는 바이러스 들 중 $m$개를 골라야한다. DFS 같은 방법으로 고를 수 있지만, next_permutation을 사용하면 간단하다.
4개 중 2개를 고르는 조합은 0011 → 0101 → 0110 → 1001 → 1010 → 1100 순으로 진행된다.

	#include <cstdio> // printf
	#include <algorithm> // next_permutation
	using namespace std;
	int main() {
	int a[4] = {0,0,1,1};
	do {
	for (int i = 0; i < 4; ++i) printf("%d ", a[i]);
	puts("");
	} while (next_permutation(a, a + 4));
	return 0;
	}

view raw next_permutation.cpp hosted with ❤ by GitHub

이런 특징을 사용하여 매번 적당히 $m$개를 선택하여 플러드 필(Flood Fill, BFS)을 한다.

모든 빈칸을 방문한다면 그 때의 탐색 시간을, 그렇지 못한다면 $\infty$을 반환하면서 모든 조합을 확인하여 최소 시간을 구한다. $m$개 중 2의 개수($\le 10$)를 고르는 조합의 수만큼 반복된다.

시간복잡도는 $O({}_{10}C_m \cdot N^2)$

코드

	#include <bits/stdc++.h>
	using namespace std;
	#define all(v) (v).begin(),(v).end()
	#define FOR(i,n) for(int i=0;i<n;++i)
	typedef pair<int, int> ii;
	const int INF = 0x3F3F3F3F;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,1,-1};
	int g[51][51];
	bool vis[51][51];
	int bfs(int n, queue<ii>& q) {
	int rest = 0;
	FOR(i, n) FOR(j, n) {
	rest += g[i][j] == 0;
	}
	int ans = 0;
	while (!q.empty()) {
	int qs = q.size();
	while (qs--) {
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	rest -= g[y][x] == 0;
	if (rest == 0) return ans;
	FOR(i, 4) {
	int ny = y + dy[i];
	int nx = x + dx[i];
	if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
	if (vis[ny][nx] || g[ny][nx] == 1) continue;
	q.push({ny, nx});
	vis[ny][nx] = true;
	}
	}
	++ans;
	}
	return INF;
	}
	int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	vector<ii> spot;
	FOR(i, n) FOR(j, n) {
	scanf("%d", &g[i][j]);
	if (g[i][j] == 2) spot.push_back({i, j});
	}
	vector<int> choice(spot.size(), 0);
	FOR(i, m) choice[spot.size() - 1 - i] = true;
	int ans = INF;
	do {
	queue<ii> q;
	memset(vis, false, sizeof(vis));
	FOR(i, spot.size()) {
	if (choice[i]) {
	q.push(spot[i]);
	vis[spot[i].first][spot[i].second] = true;
	}
	}
	ans = min(ans, bfs(n, q));
	} while (next_permutation(all(choice)));
	printf("%d\n", ans < INF ? ans : -1);
	return 0;
	}

view raw boj-17142.cpp hosted with ❤ by GitHub