(c++)백준 14502번: 연구소

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

14502번: 연구소

[풀이]

벽 3개를 새로 새우는 모든 경우의 수에 대해 바이러스가 확산되고 나서의 안전영역을 구하는 문제였다.

먼저 dfs로 이차원 배열의 조합을 구하면서 각 케이스마다 bfs를 이용하여 바이러스가 확산됐을 때의 빈칸의 개수를 구하면 된다.

 

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

struct Pos {
	int x, y;
};

int N, M;
int Map[8][8];
int cMap[8][8];
const int dx[] = { -1,1,0,0 };//상하
const int dy[] = { 0,0,-1,1 };//좌우
int Max = -1;

//바이러스 확산
void bfs() {
	queue<Pos>q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cMap[i][j] = Map[i][j];
			if (cMap[i][j] == 2) {
				q.push({ i,j });
			}
		}
	}
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		cMap[x][y] = 2;
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (cMap[nx][ny] == 0) {
				q.push({ nx,ny });
			}
		}
	}
	
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (cMap[i][j] == 0)
				cnt++;
		}
	}
	if (Max < cnt)
		Max = cnt;
}

//dfs, 이차원 배열의 조합 구하기
void setWall(int x, int y, int cnt) {
	if (cnt == 3) {
		bfs();
		return;
	}
	for (int i = x; i < N; i++) {
		for (int j = y; j < M; j++) {
			if (Map[i][j] == 0) {
				Map[i][j] = 1;
				setWall(i, j, cnt + 1);
				Map[i][j] = 0;
			}
		}
		y = 0;
	}
}

void solution() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
		}
	}
	setWall(0, 0, 0);
	cout << Max << '\n';
}

int main() {
	solution();
	return 0;
}