백준 14502 - 연구소

문제링크

• 백준 14502

문제설명

• N x M 크기의 연구소가 주어지고 0은 빈칸, 1은 벽, 2는 바이러스를 의미한다.
• 바이러스는 인접한 상하좌우로 퍼져나갈 수 있는데, 벽을 추가로 3개를 세워서 바이러스가 퍼지지 않는 영역의 최댓값을 구하라

문제접근

• 새로운 벽을 세울 수 있는 좌표를 vector<pair<int,int>> cand 컨테이너에 담는다.
• 재귀호출을 통해 cand 에 담긴 좌표 중 3개를 뽑아 조합을 만든다.
• 만들어진 조합의 해당하는 위치에 벽(1)을 세운다.
• BFS 를 통해 바이러스를 확산한다.
• 확산이 완료된 후 바이러스가 퍼지지 못한 구역(0)의 개수를 센다.
• 위 과정을 반복하여 최댓값을 계산한다.

구현1

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>

#define NEW_WALL_CNT 3

using namespace std;

int N, M;
int board[8][8] = { 0, };
int nboard[8][8];
int visited[100] = { false, };
vector<pair<int, int>> cand;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void setVirus(int xpos, int ypos) {
	queue<pair<int, int>> q;
	q.push(make_pair(xpos, ypos));

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cpos.first + dx[dir];
			int ny = cpos.second + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (nboard[nx][ny] == 0) {
				nboard[nx][ny] = 2;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

int countNoVirus() {
	int ret = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (nboard[r][c] == 0) ret++;
		}
	}
	return ret;
}

int getSafeArea(int v, int cnt) {
	if (cnt == NEW_WALL_CNT) {
		memcpy(nboard, board, sizeof(board));
		// find virus
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (board[r][c] == 2) {
					setVirus(r, c);
				}
			}
		}
		return countNoVirus();
	}

	int ret = 0;
	for (int i = v; i < cand.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		int nxpos = cand[i].first;
		int nypos = cand[i].second;
		board[nxpos][nypos] = 1;
		ret = max(ret, getSafeArea(i + 1, cnt + 1));
		visited[i] = false;
		board[nxpos][nypos] = 0;
	}
	return ret;
}

// 새로운 벽을 둘 수 있는 좌표
void updateCand() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (board[r][c] == 0)
				cand.push_back(make_pair(r, c));
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &N, &M);

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &board[r][c]);
		}
	}

	int ans = 0;
	updateCand();
	ans = getSafeArea(0, 0);
	printf("%d\n", ans);
	return 0;
}

구현2

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>

#define MAX_CAND 64
#define MAX_N_M 8
#define EMPTY 0
#define WALL 1
#define VIRUS 2
#define EXTRA_WALL_CNT 3
using namespace std;

int N, M;
int board[MAX_N_M][MAX_N_M];
int bfsBoard[MAX_N_M][MAX_N_M];
int virusVisited[MAX_N_M][MAX_N_M];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<pair<int, int>> cand;
bool candVisited[MAX_CAND];
int firstWallCnt = 0;

int bfs(int sx, int sy)
{
	int ret = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	virusVisited[sx][sy] = true;
	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cpos.first + dx[dir];
			int ny = cpos.second + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (bfsBoard[nx][ny] == EMPTY) {
				virusVisited[nx][ny] = true;
				bfsBoard[nx][ny] = VIRUS;
				q.push(make_pair(nx, ny));
				ret++;
			}
		}
	}
	return ret;
}

int getSafeArea()
{
	int totalCount = N * M;
	int wallCount = firstWallCnt + 3;
	int virusCount = 0;
	memcpy(bfsBoard, board, sizeof(board));
	memset(virusVisited, false, sizeof(virusVisited));
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (bfsBoard[r][c] == VIRUS && virusVisited[r][c] == false) {
				virusCount += bfs(r, c);
			}
		}
	}
	return totalCount - wallCount - virusCount;
}

int makeWall(int v, int cnt)
{
	if (cnt == EXTRA_WALL_CNT) {
		return getSafeArea();
	}

	int ret = 0;
	for (int i = v; i < cand.size(); i++) {
		if (candVisited[i]) continue;
		candVisited[i] = true;
		board[cand[i].first][cand[i].second] = WALL;
		ret = max(ret, makeWall(i + 1, cnt + 1));
		candVisited[i] = false;
		board[cand[i].first][cand[i].second] = EMPTY;
	}
	return ret;
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N >> M;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			cin >> board[r][c];
			if (board[r][c] == EMPTY) cand.push_back(make_pair(r, c));
			else if (board[r][c] == WALL) firstWallCnt++;
		}
	}

	memset(candVisited, false, sizeof(candVisited));
	cout << makeWall(0, 0) << endl;
}