[백준 14502] 연구소 C++

# 문제링크

www.acmicpc.net/problem/14502

14502번: 연구소

비슷한 문제를 풀어봐서 금방 풀었다. map 크기는 8 * 8 이 최대고, 세울 수 있는 벽은 세 개이다. 맵이나 depth가  이렇게 작으면 노가다로 풀어도 된다.

 

1) map 에서 0인 좌표 중에 벽을 세울 위치 세 군데를 DFS로 고른다. (chk배열에 true로 체크)

2) 해당 위치에 벽을 세워주고 바이러스 위치부터 BFS를 돌린다. map에 직접 바이러스(2) 표시를 한다.

3) 이후 안전한 공간의 개수를 세주고, map을 원상복구 시킨다.

 

map을 원상복구 시키기 위하여, 입력 받을 때 배열 C에 map을 저장해두었다.

 

 

# 제출 코드 

 

# include <cstdio>
#include <queue>
using namespace std;

int N, M;
int map[10][10];
int C[10][10]; //원상 복구를 위한 원본 저장

int ans;
struct st {
	int y;
	int x;
};
st wall[70]; // 벽을 세울 수 있는 위치
int wi; //wall index

queue<pair<int, int>> virus;

bool chk[70]; // 벽을 세울 위치 체크

void Input() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 0) {
				wall[wi].y = i;
				wall[wi].x = j;
				wi++;
			}
			else if (map[i][j] == 2) {
				virus.push({ i,j });
			}
			C[i][j] = map[i][j]; // 원본 C에 저장해두기 
		}
	}
}

int xd[] = { 1, -1, 0,0 };
int yd[] = { 0, 0, -1 ,1 };
void BFS() {
	queue <pair<int, int>> q;
	q = virus;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];
			if (ny < 0 || ny >= N)continue;
			if (nx < 0 || nx >= M)continue;
			if (map[ny][nx] != 0)continue;
			map[ny][nx] = 2;
			q.push({ ny,nx });
		}
	}
}
void Get_max() {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) cnt++;
		}
	}
	if (cnt > ans) ans = cnt;
}
void Copy() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j] = C[i][j];
		}
	}
}
void DFS(int node, int start) {
	if (node == 3) {
		int cnt = 0;
		for (int i = 0; i < wi; i++) {
			if (chk[i] == true) { map[wall[i].y][wall[i].x] = 1; cnt++; }
			if (cnt == 3)break;
		}
		BFS();
		Get_max();
		Copy();
		return;
	}
	for (int i = start; i < wi; i++) {
		chk[i] = true;
		DFS(node + 1, i + 1);
		chk[i] = false;
	}
}
int main() {
	Input();
	DFS(0, 0);
	printf("%d\n", ans);
}