취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17142번 문제인 연구소 3이다.
문제는 아래 링크를 확인하자.

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

주어진 조건 중 입력으로 주어지는 2의 개수는 10 이하라는 점에 주목하자. 이러한 경우, 바이러스를 놓을 수 있는 경우의 수는 많아야 252가지가 되므로 모든 바이러스를 놓을 수 있는 조합에 대하여 BFS를 시도해보는 것으로 문제를 해결할 수 있게 된다.

문제에서 요구하는 시간은 연구소의 모든 "빈 칸"에 바이러스가 있게 되는 시간으로, 비활성화된 바이러스가 있는 칸의 바이러스까지 꼭 활성화시켜야하는 것은 아님에 유의하자.

입력예제 7번과 같이 빈 칸이 주어지지 않는다면 답은 0이 되는 점에 유의하자.

구현거리가 많은 문제이다. 구현에 유의하자.

아래는 제출한 소스코드이다.

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

int N, M, S;
int board[50][50];
vector<pair<int, int>> vir;
vector<pair<int, int>> stk;

int dist[50][50];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

bool exist0 = 0;
int ans = 1000000007;

void bfs() {
	memset(dist, 0, sizeof(dist));
	queue<pair<int, int>> que;
	for (auto& p : stk) {
		dist[p.first][p.second] = 1;
		que.push(p);
	}

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (-1 < rr && rr < N && -1 < cc && cc < N) {
				if (dist[rr][cc] == 0 && board[r][c] != 1) {
					dist[rr][cc] = dist[r][c] + 1;
					que.push(make_pair(rr, cc));
				}
			}
		}
	}
	int mx = 0; bool chk = 1;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c] == 0) {
				if (dist[r][c] == 0) chk = 0;
				else mx = max(mx, dist[r][c]);
			}
		}
	}

	if (chk) ans = min(ans, mx);
}

void func(int idx) {
	if (stk.size() == M) {
		bfs();
		return;
	}
	if (idx == S) return;
	func(idx + 1);
	stk.emplace_back(vir[idx]);
	func(idx + 1);
	stk.pop_back();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
			if (board[r][c] == 0) exist0 = 1;
			else if (board[r][c] == 2) vir.emplace_back(make_pair(r, c));
		}
	}

	S = vir.size();
	func(0);

	if (!exist0) cout << 0;
	else if (ans == 1000000007) cout << -1;
	else cout << ans - 1;
}